美团笔试，和为k的倍数的最长子串长度（DP方法）

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n, k;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i];
    cin >> k;
    //dp[i][j]记录以p[i]结尾的子串中，子串和对k求余为j的最远index
    vector<vector<int>> dp(n, vector<int>(k, -1));
    dp[0][p[0] % k] = 0;

    int ans = 0;
    if (p[0] % k == 0)
        ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < k; j++) {
            p[i] %= k;
            int temp = (k + j - p[i]) % k;
            if (dp[i - 1][temp] != -1)
                dp[i][j] = dp[i - 1][temp];
            if (j == 0 && dp[i][j] != -1) {
                if (i - dp[i][j] + 1 > ans)
                    ans = i - dp[i][j] + 1;
            }
        }
        if (dp[i][p[i]] == -1)
            dp[i][p[i]] = i;
		if (p[i] == 0)
            ans = ans == 0 ? 1 : ans;
    }
    cout << ans;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n, k;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i];
    cin >> k;
    vector<int> dp1(k, -1); //改为2个1维数组
    vector<int> dp2(k, -1); 
    dp1[p[0] % k] = 0;

    int ans = 0;
    if (p[0] % k == 0)
        ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < k; j++) {
            p[i] %= k;
            int temp = (k + j - p[i]) % k;
            if (dp1[temp] != -1)
                dp2[j] = dp1[temp];
            if (j == 0 && dp2[j] != -1) {
                if (i - dp2[j] + 1 > ans)
                    ans = i - dp2[j] + 1;
            }
        }
        if (dp2[p[i]] == -1)
            dp2[p[i]] = i;
        if (p[i] == 0)
            ans = ans == 0 ? 1 : ans;
        dp1 = dp2;
        dp2 = vector<int>(k, -1);
    }
    cout << ans;
    return 0;
}