Find the Maximum Length of a Good Subsequence I

• State Definition: Let dp[i][j] be the maximum length of a good subsequence that ends with the element nums[i] and has exactly j mismatches.
• Initialization:
  • Create a 2D array dp of size n x (k+1), where n is the length of nums.
  • Initialize all entries dp[i][j] to 1. This represents the base case where the subsequence consists of only the element nums[i], which has a length of 1 and 0 mismatches.
• Transitions:
  • Iterate through the array nums with index i from 0 to n-1.
  • For each i, iterate through all previous indices p from 0 to i-1.
  • For each pair (i, p), we consider extending the subsequences that ended at p with the element nums[i].
    • Case 1: nums[i] == nums[p]
      • If the current element nums[i] is the same as the previous element nums[p], no new mismatch is created.
      • We can extend any subsequence ending at p with j mismatches. The new length will be 1 + dp[p][j].
      • So, for each j from 0 to k, we update: dp[i][j] = max(dp[i][j], 1 + dp[p][j]).
    • Case 2: nums[i] != nums[p]
      • If nums[i] is different from nums[p], a new mismatch is created.
      • We can extend a subsequence ending at p that had j-1 mismatches. This is only possible if j > 0.
      • The new length will be 1 + dp[p][j-1].
      • So, for each j from 1 to k, we update: dp[i][j] = max(dp[i][j], 1 + dp[p][j-1]).
• Final Answer:
  • The problem asks for the maximum length of a good subsequence with at most k mismatches. This means we need to find the maximum value in the entire dp table, as any entry dp[i][j] represents a valid good subsequence.
  • The overall maximum length is the maximum value found in dp after all iterations.

The core idea is to build up solutions for subsequences of increasing length. For each element nums[i], we consider it as the potential end of a new, longer subsequence. We look back at all preceding elements nums[p] and see if we can append nums[i] to a subsequence ending at nums[p]. The number of mismatches j is a crucial part of our state, as it determines whether we can append nums[i] if it's different from nums[p]. By systematically building this dp table, we ensure that we have considered all possible valid subsequences.

1class Solution {2    public int maximumLength(int[] nums, int k) {3        int n = nums.length;4        // dp[i][j]: max length of a good subsequence ending at index i with j mismatches.5        int[][] dp = new int[n][k + 1];6        int maxLength = 0;7 8        for (int i = 0; i < n; i++) {9            // Initialize dp table for index i. A single element has length 1 and 0 mismatches.10            for (int j = 0; j <= k; j++) {11                dp[i][j] = 1;12            }13 14            // Iterate through all previous elements to extend their subsequences.15            for (int p = 0; p < i; p++) {16                if (nums[i] == nums[p]) {17                    // No new mismatch.18                    for (int j = 0; j <= k; j++) {19                        dp[i][j] = Math.max(dp[i][j], 1 + dp[p][j]);20                    }21                } else {22                    // New mismatch is created.23                    for (int j = 1; j <= k; j++) {24                        dp[i][j] = Math.max(dp[i][j], 1 + dp[p][j - 1]);25                    }26                }27            }28        }29 30        // The answer is the maximum value in the entire dp table.31        for (int i = 0; i < n; i++) {32            for (int j = 0; j <= k; j++) {33                maxLength = Math.max(maxLength, dp[i][j]);34            }35        }36        return maxLength;37    }38}