wittybull7's blog

By wittybull7, history, 7 weeks ago, In English

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

UPD -> Link : https://leetcode.com/problems/burst-balloons/

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wouldnt the greedy approach work for this one?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No it would not arr = [2 1 3 5]
    you need to remove 1, then 3, then 5.

»
7 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

What are the constraints? I might have an O(n^2) dp solution.

»
7 weeks ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Doesn't order matter ?

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

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

This is the exact same problem: link

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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