Make Array Non-decreasing

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.

• 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].

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.

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