給你一個整數數組?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^3
• 1 <= nums[i] <= 10^7
• 1 <= k <= 10^3

分析：

根據有效子序列的定義，可以發現，子序列中所有奇數下標的元素模 k 同余，偶數下標的元素模 k 同余。考慮子序列最后兩個元素的模 k 的余數，一共有 k^2?種可能性。用二維數組 dp 來表示子序列的最大長度，dp[i][j] 表示一個有效子序列，最后兩個元素模 k 的余數分別是 i 和 j，它的最大長度。

遍歷 nums 來更新 dp[i][j]。每遍歷到一個數字 num，我們就試圖將其加入子序列。具體來說，此時最后一個元素模 k 為 nummodk=curr，然后我們遍歷前一個元素模 k 所有的可能性 prev，將 dp[prev][curr] 更新為 dp[curr][prev]+1。最后返回二維數組的最大值即可。

int maximumLength(int* nums, int numsSize, int k) {int dp[k+5][k+5];memset(dp,0,sizeof(dp));int ans=0;for(int i=0;i<numsSize;++i){int cnt=nums[i]%k;for(int pre=0;pre<k;++pre){dp[pre][cnt]=dp[cnt][pre]+1;ans=fmax(ans,dp[pre][cnt]);}}return ans;
}