CareerCup

Assuming that

- Ai-1 = 1 when i <0
- Ai+1 = 1 when i > A.length
- The array is unsorted and should not be sorted

One solution is to scan the entire array for the maximum coins, then pop that balloon until no balloons remain.

function maxCoins(arr) {
  var coins = 0;
  while(array.length > 0) {
   // find balloon that would yield most coins
   var i = findBalloonIndexWithHighestYield(arr); // This function name would probably be abbreviated on a whiteboard 
      
     coins += calculateYield(arr, i);
     arr.splice(i, 1); // Pop balloon
   }

  return coins;
}


function findBalloonIndexWithHighestYield(arr) {
   var maxIndex = 0;
   for(var i = 1; i < arr.length; i++) {
     if(calculateYield(arr, i-1) > calculate(arr, i)) {
       maxIndex = i;
     }
   }

   return maxIndex;
}

function calculateYield(arr, index) {
   var left = 1;  
   var right = 1;
   if (index > 0) { 
      left = arr[index-1];
   }

   if (index < arr.length-1) {
     right = arr[index+1];
   }
   
   return left * right;
}

This algorithm would run in O(n^2) since every element is scanned n times in the worst case.

Information insufficient. If i-1 and i+1 become adjacent, how do we get the answer 20.

int ans(int arr[], int l, int r, int n)
{
int mscore = 0;
for (int i = l + 1; i < r; i++)
{
int cscore = ans(arr, l, i, n) + ans(arr, i, r, n);
if (l == 0 && r == n)
{
cscore += arr[i];
}
else
{
cscore += arr[l] * arr[r];
}
mscore = max(mscore, cscore);
}
return mscore;
}

int main(){


int n;
cin>> n;
int a[n+2];
a[0]=1;
a[n+1]=1;

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

cout<<ans(a,0,n+1,n+1);

}

int ans(int arr[], int l, int r, int n)
{
int mscore = 0;
for (int i = l + 1; i < r; i++)
{
int cscore = ans(arr, l, i, n) + ans(arr, i, r, n);
if (l == 0 && r == n)
{
cscore += arr[i];
}
else
{
cscore += arr[l] * arr[r];
}
mscore = max(mscore, cscore);
}
return mscore;
}

int main(){


int n;
cin>> n;
int a[n+2];
a[0]=1;
a[n+1]=1;

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

cout<<ans(a,0,n+1,n+1);

}