Scale Engineer

Find Maximum Non-decreasing Array Length

Hard
#2625Time: O(N^2), where N is the length of `nums`. The two nested loops for `i` and `j` lead to a quadratic number of operations.Space: O(N), where N is the length of `nums`. We use arrays `prefix`, `dp`, and `last`, each of size N+1.
Patterns
Dynamic Programming
Algorithms
Binary Search
Data structures
ArrayStackMonotonic StackQueueMonotonic Queue

Prompt

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.

 

Example 1:

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:

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

Example 3:

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 <= 105
  • 1 <= nums[i] <= 105

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. We define a DP state dp[i] as the maximum length of a non-decreasing array that can be formed from the prefix nums[0...i-1]. To ensure we can extend our non-decreasing sequence, we also need to keep track of the value of the last element. To maximize our chances for future extensions, we should aim for the smallest possible last element. Therefore, we use another array, last[i], to store the minimum sum of the last segment for an array of length dp[i].

The transition involves iterating through all possible previous states. For each i, we consider every possible split point j < i. This means we take an optimal solution for the prefix nums[0...j-1] and append a new element formed by summing the subarray nums[j...i-1]. If this new element is greater than or equal to the last element of the solution for nums[0...j-1], we have a valid candidate for the solution for nums[0...i-1]. We take the best among all such candidates.

Algorithm

  • Create a prefix sum array prefix to quickly calculate the sum of any subarray. prefix[i] will store the sum of nums[0...i-1].
  • Initialize two arrays, dp[n+1] and last[n+1]. dp[i] will store the maximum length of a non-decreasing array using the prefix nums[0...i-1], and last[i] will store the minimum possible sum of the last element for that length.
  • Set base cases: dp[0] = 0 and last[0] = 0 for an empty prefix.
  • Iterate from i = 1 to n. For each i, we want to compute dp[i] and last[i].
  • To do this, iterate through all possible split points j from 0 to i-1. A split at j means the last segment of our new array is the sum of nums[j...i-1], and the previous part is an optimal arrangement of nums[0...j-1].
  • The sum of the new last segment is currentSum = prefix[i] - prefix[j].
  • For the new array to be non-decreasing, currentSum must be greater than or equal to last[j].
  • If the condition currentSum >= last[j] holds, we can form a new array of length dp[j] + 1.
  • We update dp[i] and last[i] to get the maximum possible length and the minimum last sum for that length:
    • If dp[j] + 1 > dp[i], we've found a longer array. Update dp[i] = dp[j] + 1 and last[i] = currentSum.
    • If dp[j] + 1 == dp[i], we've found an array of the same maximum length. We update last[i] = min(last[i], currentSum) to make it easier for future elements.
  • After the loops complete, dp[n] will hold the maximum length for the entire array.

Walkthrough

The core of this method is a nested loop structure. The outer loop iterates through each possible end position i of a prefix of nums, from 1 to n. The inner loop iterates through all possible split points j for that prefix. For each pair (i, j), we calculate the sum of the subarray nums[j...i-1] and check if it can extend the non-decreasing array ending at j-1.

To efficiently calculate subarray sums, we precompute a prefix sum array. prefix[k] = nums[0] + ... + nums[k-1]. The sum of nums[j...i-1] is then prefix[i] - prefix[j].

Here is the implementation in Java:

class Solution {    public int findMaximumLength(int[] nums) {        int n = nums.length;        long[] prefix = new long[n + 1];        for (int i = 0; i < n; i++) {            prefix[i + 1] = prefix[i] + nums[i];        }         int[] dp = new int[n + 1];        long[] last = new long[n + 1];        // dp[0] = 0, last[0] = 0 for an empty prefix         for (int i = 1; i <= n; i++) {            // Initialize with a default value before checking predecessors            dp[i] = 0;             last[i] = Long.MAX_VALUE;             for (int j = 0; j < i; j++) {                long currentSum = prefix[i] - prefix[j];                if (currentSum >= last[j]) {                    int newLength = dp[j] + 1;                    if (newLength > dp[i]) {                        dp[i] = newLength;                        last[i] = currentSum;                    } else if (newLength == dp[i]) {                        last[i] = Math.min(last[i], currentSum);                    }                }            }        }        return dp[n];    }}

Complexity

Time

O(N^2), where N is the length of `nums`. The two nested loops for `i` and `j` lead to a quadratic number of operations.

Space

O(N), where N is the length of `nums`. We use arrays `prefix`, `dp`, and `last`, each of size N+1.

Trade-offs

Pros

  • It is a straightforward and relatively easy-to-understand application of dynamic programming.

  • The logic directly follows the problem definition.

Cons

  • The O(N^2) time complexity is too slow for the given constraints (N up to 10^5), leading to a Time Limit Exceeded (TLE) error on larger test cases.

Solutions

class Solution {public  int findMaximumLength(int[] nums) {    int n = nums.length;    long[] s = new long[n + 1];    for (int i = 0; i < n; ++i) {      s[i + 1] = s[i] + nums[i];    }    int[] f = new int[n + 1];    int[] pre = new int[n + 2];    for (int i = 1; i <= n; ++i) {      pre[i] = Math.max(pre[i], pre[i - 1]);      f[i] = f[pre[i]] + 1;      int j = Arrays.binarySearch(s, s[i] * 2 - s[pre[i]]);      pre[j < 0 ? -j - 1 : j] = i;    }    return f[n];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem