本文涉及知识点

C++动态规划

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

给你一个整数数组 nums 和一个 正 整数 k 。
nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：
(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == … == (sub[x - 2] + sub[x - 1]) % k
返回 nums 的 最长有效子序列 的长度。
示例 1：
输入：nums = [1,2,3,4,5], k = 2
输出：5
解释：
最长有效子序列是 [1, 2, 3, 4, 5] 。
示例 2：
输入：nums = [1,4,2,3,1,4], k = 3
输出：4
解释：
最长有效子序列是 [1, 4, 1, 4] 。
提示：
2 <= nums.length <= 10³
1 <= nums[i] <= 10⁷
1 <= k <= 10³

动态规划

(nums[i-1]+nums[i])%k = (nums[i]+nums[i+1])%k $\to$ nums[i-1]%k == nums[i+1]%k
先将nums[i] %= k。

动态规划的状态表示

dp[i][k] 表示最后选择的是k，倒数第二个选择的是j的最长子序列。空间复杂度：O(kk)

动态规划的填表顺序

依次枚举nums

动态规划的转移方程

for( x : nums){
y = 0 to k-1
dp[y][x] = dp[x][y]+1;
}

动态规划的初始值

dp全部为0

动态规划的返回值

dp.back()的最大值

代码

核心代码

class Solution {
		public:
			int maximumLength(vector<int>& nums, int k) {
				vector<vector<int>> dp(k, vector<int>(k));
				int ans = 0;
				for (const auto& x : nums) {
					for (int y = 0; y < k; y++)
					{
						dp[x % k][y] = max(dp[x % k][y], dp[y][x % k] + 1);
						ans = max(ans, dp[x % k][y]);
					}
				}
				return ans;
			}
		};

单元测试

vector<int> nums;
			int k;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1, 2, 3, 4, 5 }, k = 2;
			auto res = Solution().maximumLength(nums, k);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,4,2,3,1,4 }, k = 3;
			auto res = Solution().maximumLength(nums, k);
			AssertEx(4, res);
		}