Problem

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 thelargest element that you can possibly obtain in the final array.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6

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 <= 10^5
  • 1 <= nums[i] <= 10^6

Solution

Method 1 – Greedy Backward Merge

Intuition

To maximize the largest element, we should merge as many elements as possible into a single value, but only when the left element is less than or equal to the right. By traversing from the end, we can greedily merge leftwards whenever possible, always keeping the largest possible sum.

Approach

  1. Start from the end of the array and initialize a running sum with the last element.
  2. Traverse backwards:
    • If the current element is less than or equal to the running sum, merge it (add to sum).
    • Otherwise, start a new sum from the current element.
    • Track the maximum sum seen so far.
  3. Return the maximum sum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    long long maxArrayValue(vector<int>& nums) {
        long long ans = 0, sum = 0;
        for (int i = nums.size() - 1; i >= 0; --i) {
            if (nums[i] <= sum) sum += nums[i];
            else sum = nums[i];
            ans = max(ans, sum);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func maxArrayValue(nums []int) int64 {
    ans, sum := int64(0), int64(0)
    for i := len(nums)-1; i >= 0; i-- {
        if int64(nums[i]) <= sum {
            sum += int64(nums[i])
        } else {
            sum = int64(nums[i])
        }
        if sum > ans { ans = sum }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public long maxArrayValue(int[] nums) {
        long ans = 0, sum = 0;
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] <= sum) sum += nums[i];
            else sum = nums[i];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun maxArrayValue(nums: IntArray): Long {
        var ans = 0L
        var sum = 0L
        for (i in nums.indices.reversed()) {
            sum = if (nums[i] <= sum) sum + nums[i] else nums[i].toLong()
            ans = maxOf(ans, sum)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxArrayValue(self, nums: list[int]) -> int:
        ans = 0
        s = 0
        for x in reversed(nums):
            if x <= s:
                s += x
            else:
                s = x
            ans = max(ans, s)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn max_array_value(nums: Vec<i32>) -> i64 {
        let mut ans = 0i64;
        let mut sum = 0i64;
        for &x in nums.iter().rev() {
            if x as i64 <= sum {
                sum += x as i64;
            } else {
                sum = x as i64;
            }
            if sum > ans { ans = sum; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    maxArrayValue(nums: number[]): number {
        let ans = 0, sum = 0;
        for (let i = nums.length - 1; i >= 0; --i) {
            if (nums[i] <= sum) sum += nums[i];
            else sum = nums[i];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each element is visited once.
  • 🧺 Space complexity: O(1), only a few variables are used.