public class BalloonBurst
{
    public static void main(String[] args)
    {
        int balloon[] = {1,2,3,4};
        int n = balloon.length;
        System.out.println("Maximum cost = " + getMaxCost(balloon, n));
    }

    static int getMaxCost(int balloon[], int n)
    {
        int table[][] = new int[n][n];

        for(int i = 1; i <= n ; i++) // this will be length of the sub array
        {
            for(int j = 0; j <= n - i; j++)
            {
                int k = i + j - 1;

                for(int l = j  ; l <= k; l++)
                {
                  int lval = 1;
                  int rval = 1;
                  if(j != 0)
                  {
                      lval = balloon[j-1];
                  }
                  if(k != n-1)
                  {
                      rval = balloon[k+1];
                  }

                  int before = 0;
                  int after = 0;
                  if(j != l)
                  {
                     before = table[j][l-1];
                  }
                  if(k != l)
                  {
                      after = table[l+1][k];
                  }
                    table[j][k] = Math.max(lval * balloon[l] * rval + before + after, table[j][k]);
                }
            }
        }

        return table[0][n-1];
    }
}