题解，这是一个求两个不相邻子区间最大和的问题，我们很容易想到1个区间最大和怎么求，dp[i]=max(dp[i-1],0)+v[i]，而这是两个区间，而且是不相邻的，可以得到以下dp公式
dp[i][j]=max(dp[i-1][j-2],dp[i][j-1])+v[j].根据数据范围，开一个二维数组肯定是会MLE的，因此应该用两个一维数组滚动存储
代码如下：
#include <iostream> #include <bits/stdc++.h> using namespace std; int d[500005]; int p[500005]; int v[500005]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { scanf("%d",&v[i]); } int mx[3]; mx[1]=-1000000000; mx[2]=-1000000000; for(int i=0;i<2;i++) { mx[2]=-1000000000; mx[1]=0; int j; fill(d,d+n+1,-100000000); for(j=2*i+1;j<=n;j++) { d[j]=max(p[j-2],d[j-1])+v[j]; //cout<<j<<' '<<p[j-2]<<' '<<d[j-1]<<endl; p[j-2]=mx[1]; mx[1]=mx[2]; mx[2]=max(d[j],mx[2]); //cout<<j<<' '<<p[j-2]<<' '<<d[j]<<endl; } p[j-1]=mx[2]; p[j-2]=mx[1]; } cout <<mx[2]<< endl; return 0; }