CODEWITHSUNDEEP
algorithmdynamic
Sarah AlHadlaq
Sarah AlHadlaq

Reputation: 31

Finding maximum value of addition/subtraction using parentheses

Given a series of numbers that are added and subtracted (for example, 4-3-5), how can I insert parentheses to find the maximum value? In my example, 4-3-5 could be:
(4-3)-5 = -4 or
4-(3-5) = +6
so the second result is the maximum. But a brute force approach will take too long for something like 4+5-8-6-3-2.

How can I find the maximum value? I assume that dynamic programming may be useful for the problem.

Upvotes: 2

Views: 2702

Answers (1)

btilly
btilly

Reputation: 46455

Dynamic programming is indeed correct. What you need are a pair of functions. One tells you, given an interval of numbers, where to divide it to get the maximum value, and what maximum value you get. The other does the same to get the minimum.

Both functions can be calculated recursively by trying each spot to divide it in, and seeing what it leads to. Specifically if you're looking for a maximum and divide at a -, you want to make the first half max and the second one min. If you're looking for a maximum and divide at a +, you want both halves max. If you're looking for a minimum and divide at a +, you want both halves min. If you're looking for a minimum and divide at a -, you want the first half min and the second one max.

For efficiency, you memoize each function. And now it should run in time O(n^3). (You have to calculate each for O(n^2) intervals, and each calculation involves looking at O(n) possible division points.)

Upvotes: 2

Related Questions