AMD Interview Question
Developer Program EngineersCountry: 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