算法1

dp

先排序
$dp[i][j]$表示前i个数分成j组，新来一个数a[i]，选择选这个数或者不选这个数
不选:$dp[i[j] = dp[i-1][j]$
选:$dp[i][j] = max(dp[u-1][j-1]+i-u+1)(u最大值i，最小值是刚好a[i]-a[u]>5的前面一个数)$

时间复杂度$O(5nk)$

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e3 + 2;
int a[N];
int dp[N][N];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n;i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n;i++)
    {
        for (int j = 1; j <= k&&j<=i;j++)
        {
            dp[i][j] = dp[i - 1][j];
            for (int u = i; a[i] - a[u] <= 5&&u>=1;u--)
                dp[i][j] = max(dp[i][j], dp[u-1][j - 1] + i - u + 1);
        }
    }
    cout << dp[n][k] << endl;
}