Find the Maximum Length of Valid Subsequence II Solution in Java

Ah, the classic problem of finding the maximum length of a valid subsequence! It’s like trying to find the longest line at a coffee shop—everyone’s in a hurry, but you just want to savor that perfect cup of coffee. In this problem, you’re given an array of integers and a number k. Your task is to find the longest subsequence such that the last number in the subsequence modulo k is equal to the next desired number modulo k. Sounds simple, right? Well, it’s like trying to find a matching sock in a pile of laundry—easy in theory, but a real challenge in practice!

C++ Solution
Python Solution

Code Solution


class Solution {
  public int maximumLength(int[] nums, int k) {
    int[][] dp = new int[k][k];
    for (final int x : nums)
      for (int y = 0; y < k; ++y)
        dp[x % k][y] = dp[y][x % k] + 1;
    return Arrays.stream(dp).flatMapToInt(Arrays::stream).max().getAsInt();
  }
}

Approach

The approach used in this solution is dynamic programming. We maintain a 2D array dp where dp[i][j] represents the maximum length of a valid subsequence where the last number modulo k is i and the next desired number modulo k is j. We iterate through each number in the input array and update our dp table accordingly. The final answer is the maximum value found in the dp table.

Time and Space Complexity

  • Time Complexity: O(n × k), where n is the length of the input array and k is the given integer.
  • Space Complexity: O(k²) due to the 2D dp array.

Real-World Example

Imagine you’re at a party, and you want to form a conga line. The rule is that the last person in the line must have a dance move that matches the next person’s move. You want to maximize the length of this conga line. Just like in our problem, you need to find the longest sequence of dance moves that can be performed in a valid manner. The solution helps you figure out how to keep the party going without any awkward dance breaks!

Similar Problems

If you enjoyed this problem, you might also like these: