Question

2789. Largest Element in an Array after Merge Operations

中文文档

Description

You are given a 0-indexed array nums consisting of positive integers.

You can do the following operation on the array any number of times:

• Choose an integer i such that 0 <= i < nums.length - 1 and nums[i] <= nums[i + 1]. Replace the element nums[i + 1] with nums[i] + nums[i + 1] and delete the element nums[i] from the array.

Return _the value of the largest element that you can possibly obtain in the final array._

 

Example 1:

Input: nums = [2,3,7,9,3]
Output: 21
Explanation: We can apply the following operations on the array:
- Choose i = 0. The resulting array will be nums = [5,7,9,3].
- Choose i = 1. The resulting array will be nums = [5,16,3].
- Choose i = 0. The resulting array will be nums = [21,3].
The largest element in the final array is 21. It can be shown that we cannot obtain a larger element.

Example 2:

Input: nums = [5,3,3]
Output: 11
Explanation: We can do the following operations on the array:
- Choose i = 1. The resulting array will be nums = [5,6].
- Choose i = 0. The resulting array will be nums = [11].
There is only one element in the final array, which is 11.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106

Solutions

Solution 1: Merge in Reverse Order

According to the problem description, in order to maximize the maximum element in the merged array, we should merge the elements on the right first, making the elements on the right as large as possible, so as to perform as many merge operations as possible and finally get the maximum element.

Therefore, we can traverse the array from right to left. For each position $i$, where $i \in [0, n - 2]$, if $nums[i] \leq nums[i + 1]$, we update $nums[i]$ to $nums[i] + nums[i + 1]$. Doing so is equivalent to merging $nums[i]$ and $nums[i + 1]$ and deleting $nums[i]$.

In the end, the maximum element in the array is the maximum element in the merged array.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $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);
}