Description
给出长度为n的序列，从中找出2个子序列，满足每个子序列相邻两数之间要么相差1，要么同余于7，求这两个子序列的最长长度和。
Sample Input
4
1 2 4 5
Sample Output
4
设f[i][j]为以i，j为结尾的子序列的最大值。
维护一个维护两个最大值，优化转移即可。
为了避免重复，转移时考虑满足i < j。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int _min(int x, int y) {return x < y ? x : y;}
int _max(int x, int y) {return x > y ? x : y;}
int read() {
int s = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * f;
}
int a[5100], b[5100], c[5100], Next[5100], Prev[5100];
int f[5100][5100];
int p[7], kk[5100];
int main() {
int n = read();
for(int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
sort(b + 1, b + n + 1); int u = 0;
for(int i = 1; i <= n; i++) if(b[i] != b[i - 1]) b[++u] = b[i];
for(int i = 1; i <= n; i++) c[i] = lower_bound(b + 1, b + u + 1, a[i]) - b;
for(int i = 1; i <= u; i++) {
if(i > 1 && b[i] == b[i - 1] + 1) Prev[i] = i - 1;
if(i < u && b[i] + 1 == b[i + 1]) Next[i] = i + 1;
}
int ans = 0, po;
for(int i = 0; i < n; i++) {
memset(p, 0, sizeof(p)), memset(kk, 0, sizeof(kk));
for(int j = 0; j < i; j++) p[a[j] % 7] = _max(p[a[j] % 7], f[j][i]), kk[c[j]] = _max(kk[c[j]], f[j][i]);
for(int j = i + 1; j <= n; j++) {
f[i][j] = f[0][i] + 1;
f[i][j] = _max(f[i][j], p[a[j] % 7] + 1);
f[i][j] = _max(f[i][j], _max(kk[Next[c[j]]], kk[Prev[c[j]]]) + 1);
p[a[j] % 7] = _max(p[a[j] % 7], f[i][j]);
kk[c[j]] = _max(kk[c[j]], f[i][j]);
if(f[i][j] > ans) ans = f[i][j], po = j;
}
} printf("%d\n", ans);
return 0;
}