Make Array Non-decreasing

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

1class Solution {2    public int makeArrayNonDecreasing(int[] nums) {3        int n = nums.length;4        if (n == 0) {5            return 0;6        }7 8        // dp[i] stores a pair: {max_size, min_last_element_value} for prefix nums[0...i]9        int[][] dp = new int[n][2];10 11        // Base case: i = 012        dp[0][0] = 1;13        dp[0][1] = nums[0];14 15        for (int i = 1; i < n; i++) {16            int bestSize = 0;17            int minLastVal = Integer.MAX_VALUE;18 19            int currentMax = 0;20            // Iterate backwards for the last segment nums[j...i]21            for (int j = i; j >= 0; j--) {22                currentMax = Math.max(currentMax, nums[j]);23                24                int prevSize = (j == 0) ? 0 : dp[j - 1][0];25                int prevLastVal = (j == 0) ? Integer.MIN_VALUE : dp[j - 1][1];26 27                if (prevLastVal <= currentMax) {28                    int currentSize = prevSize + 1;29                    if (currentSize > bestSize) {30                        bestSize = currentSize;31                        minLastVal = currentMax;32                    } else if (currentSize == bestSize) {33                        minLastVal = Math.min(minLastVal, currentMax);34                    }35                }36            }37            dp[i][0] = bestSize;38            dp[i][1] = minLastVal;39        }40 41        return dp[n - 1][0];42    }43}