算法1

(DP) $O(n^2)$

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 5010;
int f[maxn][maxn], a[maxn], cnt[maxn];

int main(void) {
    int n, k; scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int l = 1;
    for(int i = 1; l <= n; ) {
        while(i <= n && a[i] - a[l] <= 5) i++;
        cnt[l] = i - l;
        l++;
    }
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= k; j++) {
            if(i-1>=0) f[i][j] = max(f[i][j], f[i-1][j]);
            if(j + 1 <= k) f[i+cnt[i+1]][j+1] = max(f[i+cnt[i+1]][j+1], f[i][j]+cnt[i+1]);
        }
    }
    printf("%d\n", f[n][k]);
    return 0;
}

// divide pre i elements to at most k groups, max amount
// f(i,j) = f(i-1,j)
// f(i,j) + cnt[i+1] = f(i+cnt[i+1],j+1)