《Musical Theme》

dp[i][j] - 表示以i，j结尾的最大序列长度，也可以是开头。

如果是为开头的话就从后向前dp了。

这题的转置，很显然发现，如果能转置，那么相邻差值肯定一样。

所以可以先去求一个差分数组再去dp。也可以边dp边算差值。

然后注意一下不重叠。因为我们的dp值中都少了一个位置，所以我们的重叠的位置差也要少一个，这样最后算ans  + 1的时候才不会出错。

然后最后一个细节，因为内存开不出所以用滚动数组。

这里滚动数组每维都需要重新清0，不然的话就会出现可能很后面的dp来使用 + 1，导致答案不正确了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e4 + 5;
const int M = 1e4 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e12
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
}
using namespace FASTIO;

int a[5005];
int dp[2][5005];//dp[i][j] - 以i，j为结尾的最大长度
int main()
{
    int n;n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    int ans = 0;
    for(int i = 1;i <= n;++i){
        memset(dp[i % 2],0,sizeof(dp[i % 2]));
        for(int j = i + 1;j <= n;++j){
            if(a[i] - a[i - 1] == a[j] - a[j - 1]) {
                int to = j - i - 1;
                dp[i % 2][j] = min(to,dp[(i + 1) % 2][j - 1] + 1);
            }
            ans = max(ans,dp[i % 2][j]);
        }
    }
    if(ans < 4) printf("0
");
    else printf("%d
",ans + 1);
      system("pause");
    return 0;
}