#include using namespace std; int n,i,j,cur,a[1010],f[1010][1010][2],r=-2000; int main() { scanf("%d",&n); for (i=0; i0) f[i][j][0]=max(f[i][j][0],f[i-1][j][0]+a[j]); f[i][j][0]=max(f[i][j][0],cur+a[j]); cur=max(cur,0)+a[j]; if (i>0) cur=max(cur,f[i-1][j][1]+a[j]); r=max(r,f[i][j][0]); } for (cur=0, j=n-1; j>=0; j--) { f[i][j][1]=a[j]; if (i>0) f[i][j][1]=max(f[i][j][1],f[i-1][j][1]+a[j]); f[i][j][1]=max(f[i][j][1],cur+a[j]); cur=max(cur,0)+a[j]; if (i>0) cur=max(cur,f[i-1][j][0]+a[j]); r=max(r,f[i][j][1]); } } printf("%d\n",r); return 0; }