Problem

You are given a 0-indexed integer array nums.

You can perform any number of operations, where each operation involves selecting a subarray of the array and replacing it with the sum of its elements. For example, if the given array is [1,3,5,6] and you select subarray [3,5] the array will convert to [1,8,6].

Return the** maximum** length of a** non-decreasing** array that can be made after applying operations.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: nums = [5,2,2]
Output: 1
Explanation: This array with length 3 is not non-decreasing.
We have two ways to make the array length two.
First, choosing subarray [2,2] converts the array to [5,4].
Second, choosing subarray [5,2] converts the array to [7,2].
In these two ways the array is not non-decreasing.
And if we choose subarray [5,2,2] and replace it with [9] it becomes non-decreasing. 
So the answer is 1.

Example 2

1
2
3

Input: nums = [1,2,3,4]
Output: 4
Explanation: The array is non-decreasing. So the answer is 4.

Example 3

1
2
3
4

Input: nums = [4,3,2,6]
Output: 3
Explanation: Replacing [3,2] with [5] converts the given array to [4,5,6] that is non-decreasing.
Because the given array is not non-decreasing, the maximum possible answer is 3.

Constraints

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

Solution

Method 1 – Dynamic Programming with Monotonic Stack

Intuition

We want to maximize the length of a non-decreasing array after repeatedly replacing any subarray with its sum. The key is that after each operation, the array shrinks, and the sum can be placed anywhere, so we can always merge adjacent non-decreasing segments. The problem reduces to finding the length of the longest non-decreasing subarray that can be formed by merging sums.

Approach

  1. Use a monotonic stack to keep track of the current non-decreasing sequence.
  2. For each number in nums, if it is less than the top of the stack, pop and merge (sum) until the stack is non-decreasing.
  3. Push the new sum onto the stack.
  4. The answer is the size of the stack at the end.

Code

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

class Solution {
public:
    int maxNonDecreasingLength(vector<int>& nums) {
        vector<long long> stk;
        for (int x : nums) {
            long long sum = x;
            while (!stk.empty() && sum < stk.back()) {
                sum += stk.back();
                stk.pop_back();
            }
            stk.push_back(sum);
        }
        return stk.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func maxNonDecreasingLength(nums []int) int {
    stk := []int64{}
    for _, x := range nums {
        sum := int64(x)
        for len(stk) > 0 && sum < stk[len(stk)-1] {
            sum += stk[len(stk)-1]
            stk = stk[:len(stk)-1]
        }
        stk = append(stk, sum)
    }
    return len(stk)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int maxNonDecreasingLength(int[] nums) {
        Deque<Long> stk = new ArrayDeque<>();
        for (int x : nums) {
            long sum = x;
            while (!stk.isEmpty() && sum < stk.peekLast()) {
                sum += stk.pollLast();
            }
            stk.addLast(sum);
        }
        return stk.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun maxNonDecreasingLength(nums: IntArray): Int {
        val stk = ArrayDeque<Long>()
        for (x in nums) {
            var sum = x.toLong()
            while (stk.isNotEmpty() && sum < stk.last()) {
                sum += stk.removeLast()
            }
            stk.addLast(sum)
        }
        return stk.size
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def maxNonDecreasingLength(self, nums: list[int]) -> int:
        stk: list[int] = []
        for x in nums:
            s = x
            while stk and s < stk[-1]:
                s += stk.pop()
            stk.append(s)
        return len(stk)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn max_non_decreasing_length(nums: Vec<i32>) -> i32 {
        let mut stk: Vec<i64> = vec![];
        for &x in &nums {
            let mut sum = x as i64;
            while let Some(&last) = stk.last() {
                if sum < last {
                    sum += stk.pop().unwrap();
                } else {
                    break;
                }
            }
            stk.push(sum);
        }
        stk.len() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    maxNonDecreasingLength(nums: number[]): number {
        const stk: number[] = [];
        for (let x of nums) {
            let sum = x;
            while (stk.length && sum < stk[stk.length-1]) {
                sum += stk.pop()!;
            }
            stk.push(sum);
        }
        return stk.length;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each element is pushed and popped at most once.
  • 🧺 Space complexity: O(n), for the stack used to track segments.