You are given an array 'arr' of 'n' balloons, where 'a[i]' represents the coins associated with 'ith' balloon.
On bursting 'ith' balloon, the number of coins collected is equal to 'a[i-1] * a[i] * a[i+1]'. Also, balloons 'i-1' and 'i+1' now become adjacent.
Find the maximum possible coins collected after bursting all the balloons. Assume an extra 1 at each boundary.
Input: 'arr' = [5,2,6,9]
Output: 384
Explanation:
The best way to burst balloons is following:
Choosing 2nd balloon, we get 5*2*6 coins. Now the array is [5,6,9].
Choosing 2nd balloon, we get 5*6*9 coins. Now the array is [5,9].
Choosing 1st balloon, we get 1*5*9 coins. Now the array is [9].
Choosing the last balloon, we get 1*9*1 coins.
Finally we get 5*2*6 + 5*6*9 + 1*5*9 + 1*9*1 = 384 coins.
There's no way to choose the order of bursting balloons such that we get more than 384 coins.
The first line of the input contains an integer 'n', size of array 'arr'.
The second line of the input contains 'n' integers, elements of array 'arr'.
Return a single integer as described in the problem statement.
You do not need to print anything, it has already been taken care of. Just implement the given function.
2
5 10
60
For the given input, best way to burst balloons is as follows:
First burst the 1st balloon collecting coins = 1*5*10. Now the array becomes [10].
Then burst the last remaining balloon collecting coins = 1*10*1.
Finally total number of coins collected = 1*5*10 + 1*10*10 = 60.
4
1 2 3 4
40
Try to solve this in O(n^3).
1 ≤ n ≤ 100
0 ≤ arr[i] ≤ 100
Try dividing this problem into independent subproblems.
Approach:
Let’s consider subarray {arr[l],...,arr[r]} of array. Let’s say the last balloon to burst in this range is at index ‘k’. Since it’s the last balloon to burst in current range coins collected for it will be ‘cur’ = ‘arr[l-1]*arr[k]*arr[r+1]’. Thus coins collected for the whole range would be coins collected in range [l,k-1] + cur + coins collected in range [k+1,r].
Thus we have divided this problem into independent sub problems:
Where coins(l,r) represents maximum coins collected for subarray {arr[l],...,arr[r]}.
We can use this to build a recursive solution.
The steps are as follows:
function coins(int l, int r, vector<int>&arr)
function burstBalloons(vector<int> arr)
O(3^n), where ‘n’ is the size of ‘arr’.
‘coins()’ function is called at most 3^n times.
Hence, the time complexity is O(3^n).
O(n), where ‘n’ is the size of ‘arr.
Depth of the recursion tree will be ‘n’.
Hence, the space complexity is O(n).
All tags
Sort by
Interview problems
c++ || solution
int burstBalloons(vector<int> &nums){
int n = nums.size();
nums.push_back(1);
nums.insert(nums.begin(),1);
vector<vector<int>> dp(n+2,vector<int>(n+2,0));
for(int i=n; i>=1; i--){
for(int j=i; j<=n; j++){
int res = INT_MIN,curr;
for(int k=i; k<=j; k++){
curr = nums[i-1]*nums[k]*nums[j+1] + dp[i][k-1] + dp[k+1][j];
res = max(curr,res);
}
dp[i][j] = res;
}
}
return dp[1][n];
}
Interview problems
memoization c++ solution
int f(vector<int>& arr,int i,int j,vector<vector<int>> &dp){
if(i>j) return 0;
if(dp[i][j]!=-1) return dp[i][j];
int maxi=-1e9;
for(int indx=i;indx<=j;indx++){
int cost=arr[i-1]*arr[indx]*arr[j+1]+f(arr,i,indx-1,dp)+f(arr,indx+1,j,dp);
maxi=max(maxi,cost);
}
return dp[i][j]=maxi;
}
int burstBalloons(vector<int> &arr){
// Write your code here.
arr.push_back(1);
arr.insert(arr.begin(),1);
int n=arr.size();
vector<vector<int>> dp(n+1,vector<int>(n+1,-1));
return f(arr,1,n-1,dp);
}
Interview problems
C++ Easy || Memoization --> Tabulation 🔥🔥
#include<bits/stdc++.h>
int burstBalloons(vector<int> &arr){
// Write your code here.
arr.push_back(1);
arr.insert(arr.begin(), 1);
int n= arr.size();
vector<vector<int>> dp(n, vector<int> (n, 0));
for(int i = n-2; i>=1; i--){
for(int j = i; j<=n-2; j++){
int maxi = INT_MIN;
for(int k = i ; k <= j ; k++){
int cost = arr[i-1]*arr[k]*arr[j+1] + dp[i][k-1]+ dp[k+1][j];
maxi = max(maxi, cost);
}
dp[i][j] = maxi;
}
}
return dp[1][n-2];
}
// int f(int i, int j, vector<int> &arr,vector<vector<int>> &dp){
// if(i> j) return 0;
// if( dp[i][j] != -1) return dp[i][j];
// int maxi = INT_MIN;
// for(int k = i ; k <= j ; k++){
// int cost = arr[i-1]*arr[k]*arr[j+1] + f(i,k-1,arr,dp)+ f(k+1, j ,arr,dp);
// maxi = max(maxi, cost);
// }
// return dp[i][j] = maxi;
// }
// int burstBalloons(vector<int> &arr){
// // Write your code here.
// arr.push_back(1);
// arr.insert(arr.begin(), 1);
// int n= arr.size();
// vector<vector<int>> dp(n, vector<int> (n, -1));
// return f(1, n-2,arr,dp);
// }
Interview problems
why this code is not working.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
int arr[N];
for(int i=0;i<N;i++){
int x;
cin>>x;
arr.push_back(x);
}
int N=arr.size();
arr.push_back(1);
arr.insert (arr.begin(),1);
vector<vector<int>> dp(N+2,vector<int>(N+2,0));
for(int i=N;i>=1;i--){
for(int j=1;j<=N;j++){
if(i>j){
continue;
}
int min1=INT_MIN;
for(int idx=i;idx<=j;idx++){
int s=arr[idx]*arr[i-1]*arr[j+1] + dp[i][idx-1] + dp[idx+1][j];
min1=max(min1,s);
}
dp[i][j]=min1;
}
}
cout<<dp[1][N];
return 0;
}
