Balloon_busrt_Samsung

/*
There are n balloons and n bullets and each balloon is assigned with a particular number (point). Whenever a particular balloon is shot the no of points increases by 1.the multiplication of point assigned to balloon on left and that of right side.

2.point assigned to left if no right exists

3.point assigned to right if no left exists.

4.the point assigned to itself if no other balloon exists.

You have to output the maximum no of points possible.

Input

1 2 3 4

Output

20
*/

#include <iostream>
using namespace std;

int n;
int dp[100][100];
int a[100];

int solve(){
    for(int i=1; i<=n; i++){
        for(int left=1; left <= n-i+1; left++){
            int right=left + i -1;
            for(int k=left; k<=right; k++){

                int temp = dp[left][k-1] + dp[k+1][right];
                if(left == 1 && right == n) temp += a[k];
                else temp += a[left-1]*a[right+1];

                dp[left][right]=max(dp[left][right],temp);

            }
        }
    }
    return dp[1][n];
}

int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>n;

        a[0]=1;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        a[n+1]=1;

        dp[100][100]={};
        int ans= solve();
        cout<<ans<<endl;
    }
}