算法1

(同余系) $O(n+k^2)$

时间复杂度

$O(n+k^2)$

参考文献

https://blog.csdn.net/m0_73669127/article/details/143944913?spm=1001.2014.3001.5501

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 1e3 + 10;
int maxx[M][4];
void consider(int r, int x)
{
  if(x > maxx[r][1])
  {
    maxx[r][3] = maxx[r][2];
    maxx[r][2] = maxx[r][1];
    maxx[r][1] = x;
  }
  else if(x > maxx[r][2])
  {
    maxx[r][3] = maxx[r][2];
    maxx[r][2] = x;
  }
  else if(x > maxx[r][3])
    maxx[r][3] = x;
}
int cal(int i, int j, int t)
{
  if(i != j && i != t && j != t)
  {
    return maxx[i][1] + maxx[j][1] + maxx[t][1];
  }
  else if(i == j && i == t && j == t)
  {
    return maxx[i][1] + maxx[i][2] + maxx[i][3];
  }
  else{
    if(i == j)
    {
      return maxx[i][1] + maxx[i][2] + maxx[t][1];
    }
    else if(i == t)
    {
      return maxx[i][1] + maxx[i][2] + maxx[j][1];
    }
    else if(j == t)
    {
      return maxx[j][1] + maxx[j][2] + maxx[i][1];
    }
  }
}
int main()
{
    int n, k;
    cin >> n >> k;

    for(int i = 0; i < k; i++)
    {
      for(int j = 1; j <= 3; j++)
      {
        maxx[i][j] = -1e8;
      }
    }

    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        int r = x % k;
        consider(r, x);
    }

    int ans = 0;
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < k; j++)
        {
            int t = (k - (i + j) % k) % k;
            ans = max(ans, cal(i, j, t));
        }
    }

    cout << ans;
}