Find Maximum Non-decreasing Array Length — Solution
Find Maximum Non-decreasing Array Length solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Find Maximum Non-decreasing Array Length is a hard coding problem on arrays, dynamic programming and binary search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Binary Search, Stack, Monotonic Stack, Queue, Monotonic Queue
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums. In one operation you choose a contiguous subarray and replace it with a single element equal to its sum — for example [1,3,5,6] can become [4,5,6] by merging [1,3]. You may perform any number of operations.
Return the maximum length of a non-decreasing array you can end up with.
Example 1
Input: nums = [5,2,2]
Output: 1
Explanation: [5,4] and [7,2] are not non-decreasing; merging everything gives [9]. No length-2 result works.
Example 2
Input: nums = [1,2,3,4]
Output: 4
Explanation: Already non-decreasing.
Example 3
Input: nums = [4,3,2,6]
Output: 3
Explanation: Merge [3,2] into 5 to get [4,5,6].
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^5
Hints for Find Maximum Non-decreasing Array Length
Hint 1
The final array is a split of
numsinto consecutive pieces whose sums are non-decreasing. Maximise the number of pieces.Hint 2
For each prefix, track the most pieces
dp[i]and, among splits achieving it, the smallest possible last piecelast[i]— a smaller last piece leaves more room for what follows.Hint 3
A prefix ending at
jcan be extended by the piecenums[j..i-1]whenpre[j] + last[j] ≤ pre[i]. Taking the largest suchjis optimal, andpre[j] + last[j]can be kept in a monotonic queue so the whole pass is linear.
How to solve Find Maximum Non-decreasing Array Length
Choose the pieces greedily from the right end of each prefix: for prefix length i, the best split ends with the shortest possible last piece that is still at least the piece before it. That is the largest j with pre[j] + last[j] ≤ pre[i], and a monotonic queue finds it in amortised O(1).
Approach
- Compute prefix sums
pre. Setdp[0] = 0,last[0] = 0, and a deque holding index 0. - For each
ifrom 1 ton: while the second index in the deque,q[1], satisfiespre[q[1]] + last[q[1]] ≤ pre[i], pop the front — later indices are better. - With
jthe front index, setdp[i] = dp[j] + 1andlast[i] = pre[i] - pre[j]. - Pop from the back every index whose key
pre[k] + last[k]is at leastpre[i] + last[i], then pushi. - Return
dp[n].
Why it works
dp is non-decreasing in i (a longer prefix can absorb its extra elements into the last piece), so among valid j the largest one has the most pieces and the smallest last piece pre[i] - pre[j] at once. A valid j stays valid for every later i because pre only grows, so front pops never discard anything needed. An index whose key is not smaller than a later index's key can never be the largest valid one, which is why the back pops keep the keys increasing.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Maximising pieces alone is not enough; ties must prefer the smallest last piece.
- Prefix sums reach
10^10— use 64-bit integers. - A greedy that merges from the left whenever a drop appears fails on inputs like
[4,3,2,6].
Reference solution
Python
from typing import List
def findMaximumLength(nums: List[int]) -> int:
n = len(nums)
pre = [0] * (n + 1)
for i, v in enumerate(nums):
pre[i + 1] = pre[i] + v
dp = [0] * (n + 1)
last = [0] * (n + 1)
q = [0] * (n + 1)
head, tail = 0, 1
for i in range(1, n + 1):
while tail - head >= 2 and pre[q[head + 1]] + last[q[head + 1]] <= pre[i]:
head += 1
j = q[head]
dp[i] = dp[j] + 1
last[i] = pre[i] - pre[j]
key = pre[i] + last[i]
while tail > head and pre[q[tail - 1]] + last[q[tail - 1]] >= key:
tail -= 1
q[tail] = i
tail += 1
return dp[n]Java
public static int findMaximumLength(int[] nums) {
int n = nums.length;
long[] pre = new long[n + 1], last = new long[n + 1];
int[] dp = new int[n + 1], q = new int[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
int head = 0, tail = 1;
for (int i = 1; i <= n; i++) {
while (tail - head >= 2 && pre[q[head + 1]] + last[q[head + 1]] <= pre[i]) head++;
int j = q[head];
dp[i] = dp[j] + 1;
last[i] = pre[i] - pre[j];
long key = pre[i] + last[i];
while (tail > head && pre[q[tail - 1]] + last[q[tail - 1]] >= key) tail--;
q[tail++] = i;
}
return dp[n];
}C++
int findMaximumLength(vector<int>& nums) {
int n = nums.size();
vector<long long> pre(n + 1, 0), last(n + 1, 0);
vector<int> dp(n + 1, 0), q(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
int head = 0, tail = 1;
for (int i = 1; i <= n; i++) {
while (tail - head >= 2 && pre[q[head + 1]] + last[q[head + 1]] <= pre[i]) head++;
int j = q[head];
dp[i] = dp[j] + 1;
last[i] = pre[i] - pre[j];
long long key = pre[i] + last[i];
while (tail > head && pre[q[tail - 1]] + last[q[tail - 1]] >= key) tail--;
q[tail++] = i;
}
return dp[n];
}JavaScript
var findMaximumLength = function(nums) {
var n = nums.length;
var pre = new Array(n + 1).fill(0);
for (var i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
var dp = new Array(n + 1).fill(0), last = new Array(n + 1).fill(0), q = new Array(n + 1).fill(0);
var head = 0, tail = 1;
for (var i = 1; i <= n; i++) {
while (tail - head >= 2 && pre[q[head + 1]] + last[q[head + 1]] <= pre[i]) head++;
var j = q[head];
dp[i] = dp[j] + 1;
last[i] = pre[i] - pre[j];
var key = pre[i] + last[i];
while (tail > head && pre[q[tail - 1]] + last[q[tail - 1]] >= key) tail--;
q[tail++] = i;
}
return dp[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming