2025-07-17 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 17

Description

Find the Maximum Length of Valid Subsequence II

You are given an integer array nums and a positive integer k.

A subsequence sub of nums with length x is called valid if it satisfies:

  • (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k.
Return the length of the longest valid subsequence of nums.

 

Example 1:

Input: nums = [1,2,3,4,5], k = 2

Output: 5

Explanation:

The longest valid subsequence is [1, 2, 3, 4, 5].

Example 2:

Input: nums = [1,4,2,3,1,4], k = 3

Output: 4

Explanation:

The longest valid subsequence is [1, 4, 1, 4].

 

Constraints:

  • 2 <= nums.length <= 103
  • 1 <= nums[i] <= 107
  • 1 <= k <= 103

Solution

class Solution {
public:
  int maximumLength(vector<int>& nums, int k) {
    vector<vector<int>> dp(k, vector<int>(k));
    for(auto n : nums) {
      n %= k;
      for(int prev = 0; prev < k; ++prev) {
        dp[prev][n] = dp[n][prev] + 1;
      }
    }
    int answer = 0;
    for(auto row : dp) {
      answer = max(answer, *max_element(row.begin(), row.end()));
    }
    return answer;
  }
};

// Accepted
// 732/732 cases passed (167 ms)
// Your runtime beats 19.15 % of cpp submissions
// Your memory usage beats 9.12 % of cpp submissions (231.9 MB)
Algorithm