Bobek's blog

Max sum — what's the optimal solution?

By Bobek, history, 7 years ago, In English

I have array with N numbers and I'm allowed to add (),+-* between to generate max sum. Unary operator is not allowed. I know the solution for only positive numbers but I don't know how to handle negatives. Could you please give me any hints or solution?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This is a typical Dynamic programming problem of Matrix chain multiplication type. Basically in negatives you cant follow greedy type that you might have thought works in only positives one.

So here we for a dp[i][j][2] where dp[i][j][0] say stores the minimum value you can generate by applying the given operations in range [i,i+1...,j]

similarly dp[i][j][1] stores the maximum value in this range.

now for a bigger range you can check all middle breakpoints and combine them accordingly. that is dp[i][j][]=combine(dp[i][k][],dp[k][j][])..just check where you get max and min and store accordingly.(If you need the whole idea or if anythings unclear comment below.)

now the answer after dp computation is stored in dp[0][n-1][1].

→ Reply