Given an array of integers
You need to make maximum profit by removing numbers until only one number remains in array.
Profit when you remove an array element i = arr[i-1] * arr[i] * arr[i+1]
after the above operation ith element is removed from array
corner elements will have profit = corner element * adjacent element
Example : [3, 5, 1, 8, 2]
- Remove 8 : profit = 1*8*2, array = [3, 5, 1, 2]
- Remove 1 : profit = 1*8*2 + 5*1*2 array = [3, 5, 2]
and so on..
Asked in an interview, no source available
Tried searching internet, no help found
UPD -> Link : https://leetcode.com/problems/burst-balloons/
Wouldnt the greedy approach work for this one?
No it would not arr = [2 1 3 5]
you need to remove 1, then 3, then 5.
What are the constraints? I might have an O(n^2) dp solution.
O(n^3) would also work
Accepted Solution
You said you might have an O(n^2) dp solution. Can you please share the idea?
Sorry to say but the O(n^2) solution doesn't seem to work.
dp[i] — answer, if we can delete only first I elements.
so dp[0] = a[0]*a[1]
how to calc dp[i]?
dp[i] = max(dp[i-1], (i>1?dp[i-2]:0)+a[i-1]*a[i]*a[i+1])
so answer is dp[n-1]
i'm not sure if it's correct
This is the exact same problem: link
Great. Now, I can verify the correctness of my solution.
UPD: It got accepted.
Thanks!
Sorry the last one is incorrect...
We still set $$$dp[i][j]$$$ as the maximum profit for range $$$[i,j]$$$.
Thus,we can split the range $$$[i,j]$$$ into $$$3$$$ parts:$$$dp[i][k-1],dp[k+1][j]$$$ and the profit of $$$d[i-1]\times d[k]\times d[j+1]$$$.
So $$$dp[i][j]=dp[i][k-1]+dp[k+1][j]+d[i-1]\times d[k] \times d[j+1]$$$ for all $$$k\in[i,j]$$$,note that if $$$i>j$$$,$$$dp[i][j]$$$ should be $$$0$$$.
Complexity is $$$O(n^3)$$$.