Question

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

English Version

题目描述

给你一个下标从 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

解法

方法一：倒序合并

根据题目描述，为了最大化合并后的数组中的最大元素，我们应该先合并右侧的元素，使得右侧的元素尽可能大，从而尽可能多地执行合并操作，最终得到最大的元素。

因此，我们可以从右向左遍历数组，对于每个位置 $i$，其中 $i \in [0, n - 2]$，如果 $nums[i] \leq nums[i + 1]$，我们就将 $nums[i]$ 更新为 $nums[i] + nums[i + 1]$。这样做，相当于将 $nums[i]$ 与 $nums[i + 1]$ 合并，并且删掉 $nums[i]$。

最终，数组中的最大元素就是合并后的数组中的最大元素。

时间复杂度 $O(n)$，其中 $n$ 为数组的长度。空间复杂度 $O(1)$。

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

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

class Solution {
public:
  long long maxArrayValue(vector<int>& nums) {
    int n = nums.size();
    long long ans = nums[n - 1], t = nums[n - 1];
    for (int i = n - 2; ~i; --i) {
      if (nums[i] <= t) {
        t += nums[i];
      } else {
        t = nums[i];
      }
      ans = max(ans, t);
    }
    return ans;
  }
};

func maxArrayValue(nums []int) int64 {
  n := len(nums)
  ans, t := nums[n-1], nums[n-1]
  for i := n - 2; i >= 0; i-- {
    if nums[i] <= t {
      t += nums[i]
    } else {
      t = nums[i]
    }
    ans = max(ans, t)
  }
  return int64(ans)
}

function maxArrayValue(nums: number[]): number {
  for (let i = nums.length - 2; i >= 0; --i) {
    if (nums[i] <= nums[i + 1]) {
      nums[i] += nums[i + 1];
    }
  }
  return Math.max(...nums);
}