LC 2789.Largest Element in an Array after Merge Operations

题目描述

这是 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

解答

方法一：贪心算法

采用反证法的思路来证明在这个题目中使用贪心算法得到的解就是问题的最优解。（也可以采用数学归纳法证明，感兴趣的可以尝试一下）

证明前提：由于可以对数组进行任意次的替换操作，即将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，所以最优解的最终数组一定是递减的数组。可以通过如下证明：

假设最优解的最终数组中存在两个非递减的数，那么仍然可以通过替换来得到一个更好的数组，替换之后的数比原有的两个数更大，而其他的数保持不变，如果这个数比替换之前的最大数还小，那么结果没有改变，替换是可行的，而如果这个数比替换之前的最大数还大，那么替换会改变结果，与最优解的假设矛盾，所以不成立，由此可得，最优解的最终数组一定是递减的。

反证法证明：首先假设存在一个最优的操作顺序 A ，其至少有一个操作的选择与贪心算法的操作的选择 B 不同，使得最终得到的数组中的最大元素值比贪心算法采取的操作顺序 B 得到的结果来得大。

在每一个步骤中，我们有两种选择，要么选择替换当前元素 nums[i] 为 nums[i] + num[i + 1] ，要么选择不进行任何的操作。

不失一般性，我们假设在第 k 个步骤时，贪心算法的操作顺序 B 和最优算法的操作顺序 A 第一次采取了不同的操作，那么存在两种情况：

1. 如果 A 在 k 时采取的步骤是替换操作，那么 B 在当前的操作就是不进行任何操作，而由贪心算法的性质知道，贪心算法会选择当前步骤中所有可行选择中的最优的局部选择，又由 A 在 k 时可以采取替换步骤知道，此时的 nums[k] 满足 nums[k] >= nums[k - 1] ，与贪心算法性质相矛盾，所以不存在这种情况。

2. 如果 A 在 k 时采取的步骤是不进行操作，那么 B 在当前的操作就是替换操作，由于 B 可以进行替换操作，所以满足 nums[k] >= nums[k - 1] ，此时不满足最优解的最终数组一定是非递减的，所以产生了矛盾，不存在这种情况。

综上所述，贪心算法的操作顺序 B 的操作顺序和最优解的操作顺序 A 是一致的，所以贪心算法得到的最终解就是最优解。

注意：这里有个小陷阱，在提示中的数字中可以看出来，最大的数可能会超过 int 的范围，所以要用 long。

class Solution {
    public long maxArrayValue(int[] nums) {
        long res = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; --i) {
            if (res < nums[i]) {
                res = nums[i];
            } else {
                res += nums[i];
            }
        }
        return res;
    }
}

• 时间复杂度：\(O(n)\)，遍历数组用了\(O(n)\)的时间，所以时间复杂度为\(O(n)\)。

• 空间复杂度：\(O(1)\)，只使用了 res 来存储最大值，所以空间复杂度为\(O(1)\)。

每题一图