Untitled

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);
    long N;
    cin>>N;

    long dp[N][N];
    long seq[N],sum[N+1];
    for(int i = 1 ; i <= N ; i++){
        cin>>seq[i];
        sum[i] = sum[i-1] + seq[i];
    }
    for(int i = 0 ; i <= N ; i++){
        for(int j = 0 ; j <= N ; j++){
            dp[i][j] = 0;
        }
    }

    for(int len = 3 ; len <= N ; len ++){
        for(int l = 1 ; l<= N-len+1 ; l ++){
            long r = l+len-1;
            dp[l][r] = -INF;
            for (int mid = l; mid < r; mid += 2){
                dp[l][r] = max(dp[l][r], dp[l][mid] + dp[mid+1][r]);
            }

            for(int i = l+1 ; i < r ; i++){
                for(int j = r-1 ; j > i ; j--){
                    dp[l][r] = max(dp[l][r],dp[l][i-1] + dp[i][j] + dp[j+1][r] + sum[i-1]*(sum[r]-sum[j]) -(sum[j] - sum[i-1]));
                }
            }
        }
    }
    cout<<dp[1][N];

    return 0;
}