wittybull7's blog

By wittybull7, history, 6 weeks ago,

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]

1. Remove 8 : profit = 1*8*2, array = [3, 5, 1, 2]
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

• +11

 » 6 weeks ago, # |   0 Wouldnt the greedy approach work for this one?
•  » » 6 weeks ago, # ^ |   0 No it would not arr = [2 1 3 5] you need to remove 1, then 3, then 5.
 » 6 weeks ago, # | ← Rev. 2 →   +9 What are the constraints? I might have an O(n^2) dp solution.
•  » » 6 weeks ago, # ^ |   +6 O(n^3) would also work
•  » » » 6 weeks ago, # ^ | ← Rev. 9 →   +10
•  » » 6 weeks ago, # ^ |   +3 You said you might have an O(n^2) dp solution. Can you please share the idea?
•  » » » 6 weeks ago, # ^ |   +6 Sorry to say but the O(n^2) solution doesn't seem to work.
 » 6 weeks ago, # | ← Rev. 3 →   +9 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
•  » » 6 weeks ago, # ^ |   0 Doesn't order matter ? The order in which the ballons are burst matters. I think your dp state doesn't take that into account.
 » 6 weeks ago, # |   +6 This is the exact same problem: link
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Great. Now, I can verify the correctness of my solution.UPD: It got accepted.
•  » » 6 weeks ago, # ^ |   0 Thanks!
 » 6 weeks ago, # | ← Rev. 3 →   0 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)$.