Leetcode3202. 找出有效子序列的最大长度 II

Every day a Leetcode

题目来源：3202. 找出有效子序列的最大长度 II

解法1：动态规划

本题是选与不选的子序列问题，可以尝试给出这样的状态定义：

dp[i][j]：以 nums[i] 结尾模 k 后值为 j 的最长子序列的长度。

那么状态转移方程是怎样的呢？对于每一个 i，遍历 j（0<=j<i），dp[i][(nums[i] + nums[j]) % k] = dp[j][(nums[i] + nums[j]) % k] + 1，保证模 k 后的值相同。

代码：

/*
 * @lc app=leetcode.cn id=3202 lang=cpp
 *
 * [3202] 找出有效子序列的最大长度 II
 */

// @lc code=start
class Solution
{
public:
    int maximumLength(vector<int> &nums, int k)
    {
        int n = nums.size();
        // dp[i][j]: 以 nums[i] 结尾模 k 后值为 j 的最长子序列的长度
        vector<vector<int>> dp(n, vector<int>(k, 1));

        int ans = 1;
        // 状态转移
        for (int i = 1; i < n; i++)
            for (int j = 0; j < i; j++)
            {
                dp[i][(nums[i] + nums[j]) % k] = dp[j][(nums[i] + nums[j]) % k] + 1;
                ans = max(ans, dp[i][(nums[i] + nums[j]) % k]);
            }
        return ans;
    }
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n²)，其中 n 是数组 nums 的长度。

空间复杂度：O(n*k)，其中 n 是数组 nums 的长度。