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 的长度。