2789.合并后数组中的最大元素

【LetMeFly】2789.合并后数组中的最大元素：贪心（倒序）

力扣题目链接：https://leetcode.cn/problems/largest-element-in-an-array-after-merge-operations/

给你一个下标从 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 <= 105
• 1 <= nums[i] <= 106

方法一：贪心（倒序）

相邻两个数，如果右边大于等于左边，则右边可以吃掉左边并化为己有。

那就从最右边往左开吃呗！若能吃，则吃之；若不能，则为之。（如果右边的数不小于左边，则右边的数吃掉左边的数；否则，右边的数成为左边的数。）

直到遍历到最左边为止。

Q&A

Q1：为什么要从右往左开吃？

A1：贪心。因为只有右边较大才能吃到左边，最终目标是总和尽可能大（也就是吃地尽可能多），因此要先大右边再大左边。例如2 2 3，若先“3吃2”则变成2 5，最终变成7；若先“2吃2”则变成4 3，无法继续。

Q2：为什么“若不能，则为之”？

A2：因为“不能”是因为“右边小于左边”，右边那个数“永无再吃之日”，并且其比左边那个数小，因此舍弃右边的数使用更大的左边的数继续。

时空复杂度

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

typedef long long ll;
class Solution {
public:
    ll maxArrayValue(vector<int>& nums) {
        ll ans = nums.back();
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (nums[i] <= ans) {
                ans += nums[i];
            }
            else {
                ans = nums[i];
            }
        }
        return ans;
    }
};

Python

from typing import List

class Solution:
    def maxArrayValue(self, nums: List[int]) -> int:
        ans = nums[-1]
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] <= ans:
                ans += nums[i]
            else:
                ans = nums[i]
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/136698122