Find the Maximum Length of a Good Subsequence II

This approach uses a straightforward dynamic programming solution. We define a 2D DP table, dp[i][j], to store the maximum length of a good subsequence ending at index i with exactly j "breaks" (where adjacent elements are different). To compute the value for dp[i][j], we iterate through all previous elements nums[p] (where p < i) and consider extending the subsequences ending at p.

• Create a 2D DP table dp[n][k+1], where dp[i][j] stores the maximum length of a good subsequence ending at index i with exactly j breaks.
• Initialize a variable maxLength to 1, as any single element is a valid subsequence of length 1.
• Iterate through each element nums[i] from i = 0 to n-1.
• For each nums[i], initialize dp[i][0] = 1 (a subsequence with just nums[i] has length 1 and 0 breaks).
• Iterate through all previous elements nums[p] where p < i.
• If nums[p] == nums[i], we can extend a subsequence ending at p without adding a break. For each j from 0 to k, update dp[i][j] = max(dp[i][j], dp[p][j] + 1).
• If nums[p] != nums[i], we introduce a new break. For each j from 1 to k, we can extend a subsequence that ended at p with j-1 breaks. Update dp[i][j] = max(dp[i][j], dp[p][j-1] + 1).
• After filling the dp table, the answer is the maximum value found in the entire dp table, as the subsequence can end at any index with any number of breaks up to k.

In this method, we define dp[i][j] as the maximum length of a good subsequence of nums[0...i] that ends with nums[i] and has exactly j breaks. A break occurs when an element is different from the previous one in the subsequence.

To compute dp[i][j], we look at all possible preceding elements nums[p] (where p < i) in the subsequence. Two cases arise:

1. nums[p] == nums[i]: If we append nums[i] to a subsequence ending in nums[p], the number of breaks does not change. Thus, we can extend any subsequence that ended at p with j breaks. The new length would be dp[p][j] + 1.
2. nums[p] != nums[i]: If we append nums[i] to a subsequence ending in nums[p], a new break is introduced. This means the subsequence ending at p must have had j-1 breaks. The new length would be dp[p][j-1] + 1.

The base case is that any single element nums[i] forms a subsequence of length 1 with 0 breaks. The final answer is the maximum value across the entire dp table, since the optimal subsequence can end at any index i and use any number of breaks j from 0 to k.

class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return 0;
        
        // dp[i][j]: max length of a good subsequence ending at index i with j breaks.
        int[][] dp = new int[n][k + 1];
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            // A subsequence with only nums[i] has length 1 and 0 breaks.
            dp[i][0] = 1;
            
            for (int p = 0; p < i; p++) {
                if (nums[p] == nums[i]) {
                    // Same element, no new break.
                    for (int j = 0; j <= k; j++) {
                        if (dp[p][j] > 0) {
                            dp[i][j] = Math.max(dp[i][j], dp[p][j] + 1);
                        }
                    }
                } else {
                    // Different element, one new break.
                    for (int j = 1; j <= k; j++) {
                        if (dp[p][j - 1] > 0) {
                            dp[i][j] = Math.max(dp[i][j], dp[p][j - 1] + 1);
                        }
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
        
        return maxLength;
    }
}