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

Doesn't order matter ?

The order in which the ballons are burst matters. I think your dp state doesn't take that into account.

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)$$$.