#2945

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Find Maximum Non-decreasing Array Length

Solve Find Maximum Non-decreasing Array Length with prefix-sum DP transitions that maximize kept segments while preserving non-decreasing merged sums.

array binary search dynamic programming stack queue

Problem Statement

You start with a 0-indexed array nums and may repeatedly merge any contiguous subarray into one value equal to that subarray's sum. After enough merges, the array becomes a sequence of segment sums taken from a partition of the original array.

Your goal is to choose a partition that produces the longest possible non-decreasing sequence of segment sums. For example, nums = [5,2,2] cannot stay length 2 in non-decreasing order after one merge, so the best valid result is a single merged value, while nums = [4,3,2,6] can become [4,5,6] by merging the middle pair.

Examples

Example 1

Input: nums = [5,2,2]

Output: 1

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

The array is non-decreasing. So the answer is 4.

Example 3

Input: nums = [4,3,2,6]

Output: 3

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

Solution Approach

Model the final array as a partition DP

Each value in the final non-decreasing array is the sum of one contiguous block from nums, so the problem becomes: partition nums into the maximum number of blocks whose sums are non-decreasing. Let dp[i] represent the best block count using the first i elements, and let the transition depend on the last block ending at i. The hard part is not the count itself, but enforcing that the new block sum is at least the previous block sum.

Use prefix sums to turn block sums into range differences

If prefix[j] is the sum of nums[0..j-1], then the block from j to i-1 has sum prefix[i] - prefix[j]. A valid transition from j to i needs this new sum to be at least the minimum required last-segment threshold carried by the best state at j. Rearranging the inequality lets you search for the earliest future index that can extend a state, which is why prefix sums and binary-searchable state frontiers fit this problem much better than checking every split.

Maintain best reachable transitions efficiently

The accepted Hard-level solution stores, for each processed prefix, both the best length and the smallest last merged sum that achieved it. As i moves forward, update the next reachable position where this state can be extended, and keep a monotonic structure so dominated states are discarded. This avoids the O(n^2) failure mode where every i scans all prior j, bringing the solution down to near-linear or O(n log n) depending on the exact implementation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

A naive state transition DP tries every previous cut for every ending index, which is O(n^2) and too slow for n up to 10^5. The optimized solution combines prefix sums with a monotonic or binary-searchable frontier of transitions, so each position is updated and queried efficiently. That reduces the runtime to O(n log n) in a standard binary-search implementation, or close to O(n) with tighter monotonic maintenance, while using O(n) extra space for DP, prefix sums, and transition bookkeeping.

What Interviewers Usually Probe

They want you to reframe repeated merge operations as partitioning nums into segment sums, not simulate array edits.
They are testing whether you can define a DP state that carries the last merged sum constraint forward.
They expect you to notice that brute-force split enumeration is the real bottleneck and replace it with prefix-sum search or a monotonic frontier.

Common Pitfalls or Variants

Common pitfalls

Using LIS-style thinking on the original numbers instead of on merged segment sums leads to the wrong state definition for Find Maximum Non-decreasing Array Length.
Tracking only dp[i] without the minimum valid last segment sum loses information and breaks future transitions.
Implementing all j-to-i transitions directly causes quadratic time and will time out on large arrays.

Follow-up variants

Return the partition itself, not just the maximum length, which requires parent reconstruction on top of the DP transitions.
Change non-decreasing to strictly increasing, which tightens the transition inequality for the next segment sum.
Allow negative numbers, which makes some monotonic assumptions weaker and forces more careful transition handling.

FAQ

What is the core pattern in Find Maximum Non-decreasing Array Length?

It is state transition dynamic programming over array partitions. Each final element is a merged segment sum, so the DP must maximize segment count while preserving a non-decreasing last-sum constraint.

Why does nums = [5,2,2] return 1?

The only length-2 outcomes come from merging either [5,2] into 7 to get [7,2] or [2,2] into 4 to get [5,4]. Both are decreasing, so the only valid non-decreasing result is merging all elements into one segment.

Why are prefix sums so important here?

They convert any candidate merged block sum into prefix[i] - prefix[j], which makes transition checks algebraic instead of iterative. That is what enables binary search or monotonic queue style optimization.

Why is a plain DP too slow for LeetCode 2945?

A plain DP checks every previous cut j for every ending index i, creating O(n^2) work. With n up to 10^5, that transition count is too large, so you need an optimized frontier of valid states.

Can this problem be solved greedily by always merging the smallest bad area?

No, local repairs do not preserve the global best partition count. A greedy merge can create a large segment sum that blocks later extensions, while the DP keeps the smallest feasible last merged sum for future growth.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def findMaximumLength(self, nums: List[int]) -> int:
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        f = [0] * (n + 1)
        pre = [0] * (n + 2)
        for i in range(1, n + 1):
            pre[i] = max(pre[i], pre[i - 1])
            f[i] = f[pre[i]] + 1
            j = bisect_left(s, s[i] * 2 - s[pre[i]])
            pre[j] = i
        return f[n]

Continue Practicing

#3420 count non decreasing subarrays after k operations #2617 minimum number of visited cells in a grid #2454 next greater element iv