Find Maximum Non-decreasing Array Length

Hard
1646.

Find Maximum Non-decreasing Array Length

Find Maximum Non-decreasing Array Length is a hard coding problem on arrays, dynamic programming and binary search, asked in Amazon and Google interviews.

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^5
  • 1 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumLength = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Find Maximum Non-decreasing Array Length

  1. Hint 1

    The final array is a split of nums into consecutive pieces whose sums are non-decreasing. Maximise the number of pieces.

  2. Hint 2

    For each prefix, track the most pieces dp[i] and, among splits achieving it, the smallest possible last piece last[i] — a smaller last piece leaves more room for what follows.

  3. Hint 3

    A prefix ending at j can be extended by the piece nums[j..i-1] when pre[j] + last[j] ≤ pre[i]. Taking the largest such j is optimal, and pre[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

  1. Compute prefix sums pre. Set dp[0] = 0, last[0] = 0, and a deque holding index 0.
  2. For each i from 1 to n: while the second index in the deque, q[1], satisfies pre[q[1]] + last[q[1]] ≤ pre[i], pop the front — later indices are better.
  3. With j the front index, set dp[i] = dp[j] + 1 and last[i] = pre[i] - pre[j].
  4. Pop from the back every index whose key pre[k] + last[k] is at least pre[i] + last[i], then push i.
  5. 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