/* Look at me! Look at me! Look at how large the monster inside me has become! */ #include #include #include #include #include #include #define FIT(a,b) for(vector::iterator a=b.begin();a!=b.end();a++) #define FITP(a,b) for(vector >::iterator a=b.begin();a!=b.end();a++) #define RIT(a,b) for(vector::reverse_iterator a=b.end();a!=b.begin();++a) #include #define ROF(a,b,c) for(int a=b;a>=c;--a) #include #include #define FOR(a,b,c) for(int a=b;a<=c;++a) #define REP(a,b) for(register int a=0;a #include #include #include #define f cin #define g cout #include #define INF 0x3f3f3f3f #define debug cerr<<"OK"; #define pii pair #define mp make_pair #define pb push_back #define fi first #define se second #define ld long double #define ll long long #define ull unsigned long long #define eps 1.e-7 #define BUFMAX 10100100 #define M 100100 #define N 1010 #define NM 2000100 #define mod 1000000007 #define eps 1.e-10 using namespace std; /* int dx[]={-1,-1,-1,0,1,1,1,0}; int dy[]={-1,0,1,1,1,0,-1,-1}; */ int n,D[2][N],L[2][N],l[2][N],r[2][N],R[2][N],p,sol; int main () { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); #endif f>>n; p=1; sol=-(1<<30); FOR(i,1,n) { if(i==3) { i++; i--; } FOR(j,1,n) f>>D[p][j]; FOR(j,1,n) { L[p][j]=R[1-p][j]+D[p][j]; l[p][j]=max(L[1-p][j],R[1-p][j])+D[p][j]; if(j!=1) L[p][j]=max(L[p][j],D[p][j]+L[p][j-1]); L[p][j]=max(L[p][j],D[p][j]); } ROF(j,n,1) { R[p][j]=L[1-p][j]+D[p][j]; r[p][j]=max(R[1-p][j],L[1-p][j])+D[p][j]; if(j!=n) R[p][j]=max(R[p][j],D[p][j]+R[p][j+1]); R[p][j]=max(R[p][j],D[p][j]); } FOR(j,1,n) { sol=max(sol,max(R[p][j],L[p][j])); R[p][j]=max(R[p][j],r[p][j]); L[p][j]=max(L[p][j],l[p][j]); } p=1-p; } g<