CUBE-025: A-Point

#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
lld qs[601],dp[601][601];

lld cut(int f,int l){
    if(f==l){return 0;}
    if(dp[f][l]!=0){return dp[f][l];}

    lld sum=0;
    for(int i=f;i<l;i++){
        lld a= qs[l]-qs[i],b=qs[i]-qs[f-1];
        if(a>b){sum=max(sum,(b*2)+a+cut(f,i)+cut(i+1,l));}
        else   {sum=max(sum,b+(a*2)+cut(f,i)+cut(i+1,l));}
    }
    return dp[f][l]=sum;
}

int main(){
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++){
        scanf("%lld",&qs[i]);
        qs[i]=qs[i]+qs[i-1];
    }
    lld ans=cut(1,n);

    printf("%lld",ans);
    return 0;
}