【LeetCode每日一题】2789. 合并后数组中的最大元素

一.题目要求

给你一个下标从 0 开始、由正整数组成的数组 nums 。
你可以在数组上执行下述操作 任意 次：
选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。
返回你可以从最终数组中获得的 最大 元素的值。

二.题目难度

中等

三.输入样例

示例 1：
输入：nums = [2,3,7,9,3]
输出：21
解释：我们可以在数组上执行下述操作：

• 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
• 选中 i = 1 ，得到数组 nums = [5,16,3] 。
• 选中 i = 0 ，得到数组 nums = [21,3] 。 最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

示例 2：
输入：nums = [5,3,3]
输出：11
解释：我们可以在数组上执行下述操作：

• 选中 i = 1 ，得到数组 nums = [5,6] 。
• 选中 i = 0 ，得到数组 nums = [11] 。 最终数组中只有一个元素，即 11 。

提示：
1 <= nums.length <= $10^5$
1 <= nums[i] <= $10^6$

四.解题思路

想到是贪心，没写出来

五.代码实现

class Solution {
public:
    long long maxArrayValue(vector<int>& nums) {
        long long Sum = nums.back();
        for (vector<int>::iterator it = nums.end() - 2; it >= nums.begin(); it--)
        {
            if (*it <= Sum)
            {
                Sum += *it;
            }
            else Sum = *it;
        }
        return Sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

六.题目总结

官方题解：
为了使数组的最大值最大，我们可以贪心地做尽可能多的合并，直到整个数组都不能进行合并。合并的要求是后面的数字不小于前面的数字，我们就尽可能先合并靠后的数字，使其尽快能大，才能够合并前面的数字。

我们从后往前倒序遍历一次数组，依次比较两个相邻的元素，如果两个相邻的元素能够合并，就将其合并。如果不能合并，就继续往前判断。因为这样的操作流程，在比较过程中，靠后的数是所有操作流程可能性中能产生的最大值，而靠前的数，是所有操作流程可能性中能产生的最小值。如果在遍历过程中，比较的结果是不能合并，那么其他任何操作流程都无法合并这两个数。如果可以合并，那我们就贪心地合并，因为这样能使接下来的比较中，靠后的数字尽可能大。

在具体实现上，我们可以倒序遍历 $nums$，然后依次比较所有 $nums[i+1]$ 和 $nums[i]$。如果 $nums[i+1]\ge nums[i]$，那么就将 $nums[i]$更新为 $nums[i+1]+nums[i]$。这样的操作相当于进行了合并，因为我们不会再访问 $nums[i+1]$。遍历完后直接返回 $nums[0]$，因为合并完后的数组肯定是递减的，否则可以继续合并，这样的话首元素就是数组最大值。