# Make Array Non-decreasing
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/make-array-non-decreasing)
Canonical: https://scaleengineer.com/dsa/problems/make-array-non-decreasing
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Stack, Monotonic Stack
---
## Problem
You are given an integer array `nums`. In one operation, you can select a subarray and replace it with a single element equal to its **maximum** value.

Return the **maximum possible size** of the array after performing zero or more operations such that the resulting array is **non-decreasing**.

**Example 1:**

**Input:** nums = \[4,2,5,3,5\]

**Output:** 3

**Explanation:**

One way to achieve the maximum size is:

1. Replace subarray `nums[1..2] = [2, 5]` with `5` → `[4, 5, 3, 5]`.
2. Replace subarray `nums[2..3] = [3, 5]` with `5` → `[4, 5, 5]`.

The final array `[4, 5, 5]` is non-decreasing with size 3.

**Example 2:**

**Input:** nums = \[1,2,3\]

**Output:** 3

**Explanation:**

No operation is needed as the array `[1,2,3]` is already non-decreasing.

**Constraints:**

* `1 <= nums.length <= 2 * 105`
* `1 <= nums[i] <= 2 * 105`

# Approaches
## Dynamic Programming
This approach uses dynamic programming to build the solution iteratively. We define a DP state `dp[i]` that stores information about the optimal partition for the prefix `nums[0...i]`. Specifically, `dp[i]` will store a pair `(size, last_val)`, representing the maximum size of a valid non-decreasing array and the minimum possible value of the last element for that maximum size.
**Time:** O(N^2), where N is the length of `nums`. There are two nested loops. The outer loop runs N times for `i`, and the inner loop runs up to `i+1` times for `j`. The work inside the inner loop is constant time because we maintain the running maximum. · **Space:** O(N) to store the DP table of size N, where each entry holds a pair of integers.
**Pros:** It is a systematic approach that correctly explores the problem space to find the optimal solution.; It serves as a good foundation for understanding the problem before moving to more optimized solutions.
**Cons:** The O(N^2) time complexity is too slow for the given constraints (N up to 2 * 10^5) and will likely result in a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
The core idea is to build the solution for `nums[0...i]` based on the solutions for smaller prefixes `nums[0...j-1]`. When we consider `nums[0...i]`, the last element of our resulting non-decreasing array must be the maximum of some subarray `nums[j...i]`. Let this maximum be `M`. For the resulting array to be non-decreasing, the element before `M` must be less than or equal to `M`. This previous element is the last element of an optimal partition for the prefix `nums[0...j-1]`.

This leads to the DP state `dp[i] = (s_i, v_i)`, where `s_i` is the maximum possible size of the non-decreasing array for the prefix `nums[0...i]`, and `v_i` is the minimum possible value of the last element among all partitions that achieve this maximum size. Minimizing the last element is a greedy choice that helps in extending the sequence later, as a smaller last element allows more options for the next element.

To compute `dp[i]`, we iterate through all possible split points `j` (from `i` down to `0`), considering `nums[j...i]` as the last group. We calculate its maximum `m = max(nums[j...i])`. We then check if `m` is greater than or equal to the last value of the optimal partition for `nums[0...j-1]`. If it is, we have found a candidate partition for `nums[0...i]`. We do this for all `j` and pick the one that maximizes the partition size, breaking ties by choosing the one with the minimum last element value.

```java
class Solution {
    public int makeArrayNonDecreasing(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        // dp[i] stores a pair: {max_size, min_last_element_value} for prefix nums[0...i]
        int[][] dp = new int[n][2];

        // Base case: i = 0
        dp[0][0] = 1;
        dp[0][1] = nums[0];

        for (int i = 1; i < n; i++) {
            int bestSize = 0;
            int minLastVal = Integer.MAX_VALUE;

            int currentMax = 0;
            // Iterate backwards for the last segment nums[j...i]
            for (int j = i; j >= 0; j--) {
                currentMax = Math.max(currentMax, nums[j]);
                
                int prevSize = (j == 0) ? 0 : dp[j - 1][0];
                int prevLastVal = (j == 0) ? Integer.MIN_VALUE : dp[j - 1][1];

                if (prevLastVal <= currentMax) {
                    int currentSize = prevSize + 1;
                    if (currentSize > bestSize) {
                        bestSize = currentSize;
                        minLastVal = currentMax;
                    } else if (currentSize == bestSize) {
                        minLastVal = Math.min(minLastVal, currentMax);
                    }
                }
            }
            dp[i][0] = bestSize;
            dp[i][1] = minLastVal;
        }

        return dp[n - 1][0];
    }
}
```
### Algorithm
- Initialize a DP array `dp` of size `N`, where `dp[i]` will store a pair `{max_size, min_last_element_value}` for the prefix `nums[0...i]`.
- Set a base case for `i=0`: `dp[0] = {1, nums[0]}`.
- Iterate `i` from `1` to `N-1` to compute `dp[i]`.
- Inside this loop, initialize `bestSize` to 0 and `minLastVal` to infinity for the current `i`.
- Start a nested loop, iterating `j` from `i` down to `0`. This `j` represents the start of the last segment `nums[j...i]`.
- In the inner loop, maintain `currentMax`, the maximum value in `nums[j...i]`.
- Get the result for the prefix `nums[0...j-1]`. If `j=0`, the previous size is 0 and the previous last value is negative infinity. Otherwise, they are `dp[j-1][0]` and `dp[j-1][1]`.
- If the previous last value is less than or equal to `currentMax`, we have a valid partition. The new size is `prevSize + 1`.
- Update `bestSize` and `minLastVal` for `dp[i]` if this new partition is better (larger size, or same size with smaller last value).
- After the inner loop finishes, store the final `bestSize` and `minLastVal` in `dp[i]`.
- The final answer is the size component of `dp[N-1]`.

## Greedy Approach with Monotonic Stack
A more efficient approach is to process the array from left to right and maintain a temporary result array that is always non-decreasing. This can be achieved using a structure that behaves like a monotonic stack. When a new number is introduced that violates the non-decreasing property, we greedily merge it with the previous element(s) by taking their maximum until the property is restored.
**Time:** O(N), where N is the length of `nums`. Each number is added to the list once. The `while` loop performs remove operations. Since each element can be removed at most once over the entire execution, the total number of operations in the `while` loop is O(N). Thus, the amortized time complexity for processing each number is O(1). · **Space:** O(N) in the worst case for the `res` list. This happens when the input array is already non-decreasing, and `res` will store all its elements.
**Pros:** Highly efficient with a linear time complexity, which is optimal.; The logic is relatively simple to implement using a list or a stack.; Passes for large constraints where O(N^2) solutions fail.
**Cons:** The greedy logic might not be immediately obvious to prove its correctness without careful reasoning.
### Explanation
This approach is based on a greedy strategy. We process the input array `nums` one element at a time and build the final non-decreasing array, let's call it `res`. We can use a list or a stack to represent `res`.

For each `num` from `nums`, we first add it to `res`. This corresponds to creating a new group `[num]`. However, this might break the non-decreasing property of `res`.

If `res` has more than one element and its last element is smaller than the one before it (`res.back() < res[res.size()-2]`), we must perform a merge operation. The two groups corresponding to the last two elements of `res` must be merged into a single group. The value of this new group is the maximum of the two merged values. So, we pop the last two elements from `res` and push their maximum back.

This merge operation might create a new violation (the new maximum might be smaller than the element before it). Therefore, we need to repeat this merging process in a loop until `res` is non-decreasing again. This behavior is characteristic of a monotonic stack (in this case, a non-decreasing one).

Let's trace `nums = [4, 2, 5, 3, 5]`:
- `res = []`
- Process `4`: `res.add(4)`. `res` is `[4]`.
- Process `2`: `res.add(2)`. `res` is `[4, 2]`. `2 < 4`, so merge. Pop `2`, pop `4`, add `max(4, 2) = 4`. `res` is `[4]`.
- Process `5`: `res.add(5)`. `res` is `[4, 5]`. `5 >= 4`, ok.
- Process `3`: `res.add(3)`. `res` is `[4, 5, 3]`. `3 < 5`, so merge. Pop `3`, pop `5`, add `max(5, 3) = 5`. `res` is `[4, 5]`. `5 >= 4`, ok.
- Process `5`: `res.add(5)`. `res` is `[4, 5, 5]`. `5 >= 5`, ok.

The final size is `res.size()`, which is 3.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int makeArrayNonDecreasing(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int num : nums) {
            res.add(num);
            while (res.size() > 1 && res.get(res.size() - 1) < res.get(res.size() - 2)) {
                int last = res.remove(res.size() - 1);
                int secondLast = res.remove(res.size() - 1);
                res.add(Math.max(last, secondLast));
            }
        }
        return res.size();
    }
}
```
### Algorithm
- Initialize an empty list or stack, let's call it `res`, to store the elements of the resulting non-decreasing array.
- Iterate through each number `num` in the input array `nums`.
- For each `num`, add it to the end of `res`.
- After adding `num`, check if `res` has at least two elements and if the last element is smaller than the second to last element (`res.get(res.size() - 1) < res.get(res.size() - 2)`).
- If the condition is true, it means the non-decreasing property is violated. To fix this, merge the last two groups: remove the last two elements from `res` and add their maximum back to `res`.
- Repeat the check and merge step in a `while` loop until the non-decreasing property is restored for `res`.
- After iterating through all numbers in `nums`, the size of `res` is the maximum possible size of the non-decreasing array.

# Solutions
### Java

```java
class Solution {
public
  int maximumPossibleSize(int[] nums) {
    int ans = 0, mx = 0;
    for (int x : nums) {
      if (mx <= x) {
        ++ans;
        mx = x;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumPossibleSize(vector<int> &nums) {
    int ans = 0, mx = 0;
    for (int x : nums) {
      if (mx <= x) {
        ++ans;
        mx = x;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumPossibleSize(self, nums: List[int]) -> int: ans = mx = 0 for x in nums: if mx <= x: ans += 1 mx = x return ans

```