3202: Find-the-Maximum-Length-of-Valid-Subsequence-II
Medium

The intuition for this algorithm is that since

(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k

had to be true, that implies that the sum of any adjacent values in a valid subsequence must be equal to a value between 0 and k-1 inclusive.

Therefore, we can iterate through all possible values of sums between 0 and k-1 inclusive and find the maximum subsequence length given a possible sum.

code

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int ans = 0;            
        for (int& num : nums) {
            num %= k;
        }

        vector<int> dp (k);
        for (int i = 0; i < k; ++i) {
            fill(dp.begin(), dp.end(), 0);
            for (int& num : nums) {
                dp[num] = dp[(k + i - num) % k] + 1;
                ans = max(ans, dp[num % k]);
            }
        }

        return ans;
    }
};

complexity

learnings

time taken