Medium

题目描述

给你一个下标从 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 ，得到数组 [5,7,9,3] 。
- 选择 i = 1 ，得到数组 [5,16,3] 。
- 选择 i = 0 ，得到数组 [21,3] 。
最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

示例 2：

输入：nums = [5,3,3]
输出：11
解释：我们可以在数组上执行下述操作：
- 选择 i = 1 ，得到数组 [5,6] 。
- 选择 i = 0 ，得到数组 [11] 。
最终数组只有一个元素，即 11 。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

解题思路

这道题的核心思路是贪心 + 逆向思维。

首先理解操作规则：只有当 nums[i] <= nums[i+1] 时，才能将两个元素合并。为了获得最大的元素，我们需要尽可能地进行合并操作。

关键观察：从右向左遍历是最优策略。因为：

  1. 如果从左向右合并，可能会错过后续更好的合并机会
  2. 从右向左遍历时，我们可以贪心地尽可能合并更多元素

具体算法：

  1. 从数组末尾开始，维护一个当前的合并值 current
  2. 向左遍历，对于每个元素 nums[i]：
    • 如果 nums[i] <= current，说明可以合并，更新 current = nums[i] + current
    • 如果 nums[i] > current，说明无法继续合并，更新 current = nums[i]
  3. 遍历过程中记录遇到的最大值

这种方法保证了我们总是在最优时机进行合并，因为从右向左遍历确保了我们不会错过任何可能的合并机会。

时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

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

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

public class Solution {
    public long MaxArrayValue(int[] nums) {
        long current = nums[nums.Length - 1];
        long maxVal = current;
        
        for (int i = nums.Length - 2; i >= 0; i--) {
            if (nums[i] <= current) {
                current += nums[i];
            } else {
                current = nums[i];
            }
            maxVal = Math.Max(maxVal, current);
        }
        
        return maxVal;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxArrayValue = function(nums) {
    let current = nums[nums.length - 1];
    let maxVal = current;
    
    for (let i = nums.length - 2; i >= 0; i--) {
        if (nums[i] <= current) {
            current += nums[i];
        } else {
            current = nums[i];
        }
        maxVal = Math.max(maxVal, current);
    }
    
    return maxVal;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组一次，n为数组长度
空间复杂度O(1)只使用常数级额外空间

相关题目