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(n2)，其中 n 是数组 nums 的长度。
空间复杂度：O(n*k)，其中 n 是数组 nums 的长度。