# Find Maximum Non-decreasing Array Length
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-maximum-non-decreasing-array-length)
Canonical: https://scaleengineer.com/dsa/problems/find-maximum-non-decreasing-array-length
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Stack, Monotonic Stack, Queue, Monotonic Queue
---
## 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.

**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
## Dynamic Programming
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.
**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.
**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.
### Explanation
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:
```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];
    }
}
```
### 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.

## Optimized DP with Monotonic Candidate List
The O(N^2) dynamic programming approach is too slow because of the inner loop that searches for the best predecessor `j` for each `i`. This search takes O(N) time. We can optimize this search to O(log N) by maintaining a special data structure.

The key observation is that we are looking for a predecessor `j` that satisfies a condition (`cost[j] <= prefix[i]`) and maximizes a value `(dp[j], prefix[j])`. Many previous candidates `j` might be suboptimal. For instance, if we have two candidates `j1` and `j2` where `j1` is better or equal in all aspects (lower cost, higher or equal length), `j2` will never be the optimal choice. 

This suggests maintaining a list of only the 'best' or non-dominated candidates. This list, which we call a monotonic candidate list `M`, will store indices `j` such that as we traverse `M`, their `cost` values and their `(dp, prefix)` values are both strictly increasing. With this sorted structure, we can use binary search to find the best predecessor for `i` in O(log N) time. The list itself can be updated in amortized constant time, leading to an overall O(N log N) solution.
**Time:** O(N log N). For each of the N elements, we perform a binary search on the monotonic list `M`, which takes O(log N) time. The update to `M` involves a while loop that, over all iterations, removes each element at most once, resulting in an amortized O(1) time per update. · **Space:** O(N), for the `prefix`, `dp`, `cost` arrays, and the monotonic list `M` which can store up to N+1 indices in the worst case.
**Pros:** Highly efficient with O(N log N) time complexity, which passes the given constraints.; Optimizes the search for the best predecessor from linear to logarithmic time.
**Cons:** The logic is significantly more complex than the O(N^2) DP approach.; Implementation requires careful handling of the monotonic candidate list and domination rules.
### Explanation
This optimized DP approach refines the state transition. The state variables `dp[i]`, `last[i]`, and the helper `prefix` array remain the same. We introduce `cost[j] = prefix[j] + last[j]` to simplify the condition for a valid predecessor.

The main improvement comes from how we find the optimal predecessor `j`. Instead of a linear scan, we use a list `M` that stores indices of pareto-optimal candidates. For an index `i` to be added to `M`, it must not be 'dominated' by any existing point in `M`. An index `k` dominates `j` if it's better on all criteria: `cost[k] <= cost[j]` and `(dp[k], prefix[k]) >= (dp[j], prefix[j])` lexicographically.

By maintaining `M` such that `cost` and `(dp, prefix)` are strictly increasing, we can efficiently query it. For each `i`, we binary search `M` for the candidate `j_best` with the largest `cost` not exceeding `prefix[i]`. This `j_best` will also have the maximal `(dp, prefix)` pair among all valid candidates.

Here is the Java implementation:
```java
import java.util.ArrayList;
import java.util.List;

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[] cost = new long[n + 1]; // cost[j] = prefix[j] + last[j]

        // Monotonic list of candidate indices
        List<Integer> m = new ArrayList<>();
        m.add(0); // Base case: empty prefix

        for (int i = 1; i <= n; i++) {
            long currentPrefix = prefix[i];

            // Binary search for the best predecessor j_best in m
            int low = 0, high = m.size() - 1;
            int j_best = 0; // Default to 0 if no other candidate is valid
            while (low <= high) {
                int midIdx = low + (high - low) / 2;
                int mid_j = m.get(midIdx);
                if (cost[mid_j] <= currentPrefix) {
                    j_best = mid_j;
                    low = midIdx + 1;
                } else {
                    high = midIdx - 1;
                }
            }
            
            dp[i] = dp[j_best] + 1;
            long last_i = currentPrefix - prefix[j_best];
            cost[i] = currentPrefix + last_i;

            // Update the monotonic candidate list m
            // Remove candidates from the end that are dominated by i
            while (!m.isEmpty()) {
                int j_back = m.get(m.size() - 1);
                boolean costDom = cost[i] <= cost[j_back];
                boolean valDom = dp[i] > dp[j_back] || (dp[i] == dp[j_back] && prefix[i] >= prefix[j_back]);
                if (costDom && valDom) {
                    m.remove(m.size() - 1);
                } else {
                    break;
                }
            }
            
            // Check if i is dominated by the new last element of m
            boolean isDominated = false;
            if (!m.isEmpty()) {
                int j_back = m.get(m.size() - 1);
                boolean costDom = cost[j_back] <= cost[i];
                boolean valDom = dp[j_back] > dp[i] || (dp[j_back] == dp[i] && prefix[j_back] >= prefix[i]);
                if (costDom && valDom) {
                    isDominated = true;
                }
            }

            if (!isDominated) {
                m.add(i);
            }
        }
        return dp[n];
    }
}
```
### Algorithm
- As with the previous approach, precompute the `prefix` sum array.
- We define `dp[i]` (max length) and `last[i]` (min last sum) as before. We also define `cost[j] = prefix[j] + last[j]`.
- The condition to extend a sequence from `j` to `i` is `prefix[i] - prefix[j] >= last[j]`, which simplifies to `cost[j] <= prefix[i]`.
- To find the best predecessor `j` for `i`, we need to find `j < i` that satisfies `cost[j] <= prefix[i]` and maximizes the pair `(dp[j], prefix[j])` lexicographically. Maximizing `prefix[j]` helps minimize the new `last[i]`.
- We maintain a monotonic list `M` of candidate indices `j`. This list stores non-dominated candidates. A candidate `j1` is non-dominated if there is no other candidate `j2` such that `cost[j2] <= cost[j1]` and `(dp[j2], prefix[j2]) >= (dp[j1], prefix[j1])`.
- The list `M` will have the property that both `cost` and `(dp, prefix)` values are strictly increasing for indices in `M`.
- For each `i` from 1 to `n`:
  1. Perform a binary search on `M` to find the rightmost index `j_best` in `M` such that `cost[j_best] <= prefix[i]`. This gives the optimal predecessor.
  2. Calculate `dp[i]`, `last[i]`, and `cost[i]` using `j_best`.
  3. Update the monotonic list `M` by adding `i`. First, remove any candidates from the end of `M` that are now dominated by `i`. Then, if `i` is not dominated by the new last element of `M`, add `i` to `M`.
- The update to `M` takes amortized O(1) time.
- The final answer is `dp[n]`.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findMaximumLength(vector<int> &nums) {
    int n = nums.size();
    int f[n + 1];
    int pre[n + 2];
    long long s[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    memset(f, 0, sizeof(f));
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= n; ++i) {
      pre[i] = max(pre[i], pre[i - 1]);
      f[i] = f[pre[i]] + 1;
      int j = lower_bound(s, s + n + 1, s[i] * 2 - s[pre[i]]) - s;
      pre[j] = i;
    }
    return f[n];
  }
};

```

### Python

```python
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]

```