## AMD Interview Question

Developer Program Engineers**Country:**India

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);

}

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.

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

- Anonymous May 15, 2016