Finding maximum value of addition/subtraction using parentheses

[zyan1zyan]

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.

[zyan1zyan]

provide a cpp code of this question using DP or anyother efficient approach.

[jonnin]

nevermind, I see. This looks fun... back in a bit
what if you wanted to group
4(-3-5) what is the answer? are you only allowed to group around the symbols as if operators, or do they sometimes mean negative values? can you have negative values?

(4+5) - ((8-6) - (3-2)) = 8 I think as best? but the algorithm...
I don't have steps. I minimized the subtractions and maximized the additions. I think its a game of recursively splitting it into smaller bits playing max - min over local groups

DP might work too, but those are hard for me to visualize.

[tpb]

As usual for these kinds of problems, the details are not entirely clear. So I'm assuming that the string consists of positive values separated by + or - operators and the parens have to go just before the numeric values (not before an operator, creating a negative value (and possibly even a multiplication)).

In that case, couldn't you just scan the string looking for two or more minuses in a row and put parens around all contiguous "subtracted terms" after the first minus?

       1st minus           1st minus
          |                   |
a + b + c - d - e + f - g + h - i - j - k - l
            ^^^^^               ^^^^^^^^^^^^^
       subtracted terms        subtracted terms

The minus between f and g doesn't matter since there are not two or more in a row.

So, no matter what the (positive) value of the letters, this grouping would maximize the result:

a + b + c - (d - e) + f - g + h - (i - j - k - l)

But maybe that's not right. I haven't thought about it much.

[helios]

But you could have the following case:
10 - 1 - 10 + 1 - 10
10 - (1 - 10 + 1 - 10) > 10 - (1 - 10) + 1 - 10

[tpb]

@helios, Good point. I should've tried to think of a counter example myself. Just being lazy I guess.

[tpb]

Another hasty guess:

The only profitable place to put a starting paren is after a minus sign (and then only if there is at least one more minus sign somewhere to the right). It's then a matter of determining how many terms should be encompassed to create the lowest value for the parenthesized group. So how about this: try a starting paren after the first negative sign and determine the position of the closing paren that creates the lowest value for that group. Then move on to the next minus sign.

  try a start paren here
    |
10 - 1 + 2 - 10 + 3 - 10 + 4 - 3 + 2 - 1
   -[1   3   -7  -4  -14  10 -13 -11 -12
                       |
                 lowest value

10 - (1 + 2 - 10 + 3 - 10) + 4 - 3 + 2 - 1
                                |
                   move on to try a start paren here

10 - (1 + 2 - 10 + 3 - 10) + 4 - 3 + 2 - 1
                               -[3   5   4
                                 |
                           lowest value

10 - (1 + 2 - 10 + 3 - 10) + 4 - (3) + 2 - 1
                                         |
                                no - signs to the right; done

(Obviously the useless parens would be removed/not put in.)

I think this would be considered a greedy algorithm. A counter example would be if greedily creating a parenthesized group means you can't create a better group that would start within it. I feel there is probably a counter example but I can't think of one. And I don't know how to prove that greed is good here.

EDIT: Thinking about this again, it seems unlikely that you can get greedy with this problem. You almost certainly need to DP this MF.

[jonnin]

10 - 1 + 2 - 10 + 3 - 10 + 4 - 3 + 2

I get 11 using the local max/min concept.

(10 - 1 + 2) - (10 + 3 - 10) + (4 - 3 + 2)
-> 11 - 3 + 3 = 11

but not sure if I did it right because I am having trouble going from human to algorithm.

a -1 appeared in the end of the above that I didnt really understand.

It seems like it can be sub-divided because the terms have a fixed order. But I am usually wrong when something 'seems like'. Here my last grouping is redundant, can omit.

[tpb]

@jonnin, I seem to have forgotten the - 1 in the first display of the equation. I've edited it to add it in.

But without it, using the method in my post above I get

10 - (1 + 2 - 10 + 3 - 10) + 4 - 3 + 2 = 27

[tpb]

I don't know if anyone is interested in this anymore, but here is a counter-example to my "greedy" idea:

   find grouping from here that produces smallest value
    |
20 - 10 - 10 + 15 - 10 - 20
    [10    0   15    5  -15
20 - (10 - 10 + 15 - 10 - 20) = 35

But
20 - (10 - 10) + 15 - (10 - 20) = 45

So greed is definitely not good here.

[nuderobmonkey]

*edit:
OOps, sorry, wrong theme. That happend because I scuffed the topic with one eye and where the other is still outside of home.

[tpb]

@nuderobmonkey, you should at least post code that compiles.
At any rate, you have totally misunderstood the problem. Your program does not solve it at all.

I'll try to create a brute-force solver so we have something to compare better solutions with.

[tpb]

Here's a brute-force solver that generates random problems to solve. It can probably be simplified. I'm assuming that the solution never needs nested parens.

Instead of trying every possible placement of non-nested parens, it only starts a group after a minus sign and only ends it after the operand after a minus sign, since those are the only useful positions to place them. Also, if a possible ending position has another subtracted term after it, then that term will also be included. And if there is a subtracted term before a possible start paren, it will be included.

It stores the problem as a vector<int> where "1 - 2 + 3 - 4" becomes {1,-2, 3,-4}. The parens are stored as a vector<pair<int,int>> where for each pair, first is the index of the operand before which the start paren goes and second is the index of the operand after which the end paren goes.

E.g., prob vector: {10,-2,3,-10,10,-3,-5}; paren vector {{1,3},{5,6}}
means "10 - (2 + 3 - 10) + 10 - (3 - 5)"

E.g. 12-operand problem solution showing attempted parenthesizations (verbose):

66 - 58 - 31 + 25 - 7 + 7 + 25 + 63 - 10 + 83 - 38 - 53 = 72
66 - (58 - 31) + 25 - 7 + 7 + 25 + 63 - 10 + 83 - 38 - 53 = 134
66 - (58 - 31) + 25 - (7 + 7 + 25 + 63 - 10) + 83 - 38 - 53 = -36
66 - (58 - 31) + 25 - (7 + 7 + 25 + 63 - 10) + 83 - (38 - 53) = 70
66 - (58 - 31) + 25 - (7 + 7 + 25 + 63 - 10 + 83 - 38 - 53) = -20
66 - (58 - 31) + 25 - 7 + 7 + 25 + 63 - (10 + 83 - 38 - 53) = 150
66 - (58 - 31) + 25 - 7 + 7 + 25 + 63 - 10 + 83 - (38 - 53) = 240
66 - (58 - 31 + 25 - 7) + 7 + 25 + 63 - 10 + 83 - 38 - 53 = 98
66 - (58 - 31 + 25 - 7) + 7 + 25 + 63 - (10 + 83 - 38 - 53) = 114
66 - (58 - 31 + 25 - 7) + 7 + 25 + 63 - 10 + 83 - (38 - 53) = 204
66 - (58 - 31 + 25 - 7 + 7 + 25 + 63 - 10) + 83 - 38 - 53 = -72
66 - (58 - 31 + 25 - 7 + 7 + 25 + 63 - 10) + 83 - (38 - 53) = 34
66 - (58 - 31 + 25 - 7 + 7 + 25 + 63 - 10 + 83 - 38 - 53) = -56
66 - 58 - 31 + 25 - (7 + 7 + 25 + 63 - 10) + 83 - 38 - 53 = -98
66 - 58 - 31 + 25 - (7 + 7 + 25 + 63 - 10) + 83 - (38 - 53) = 8
66 - 58 - 31 + 25 - (7 + 7 + 25 + 63 - 10 + 83 - 38 - 53) = -82
66 - 58 - 31 + 25 - 7 + 7 + 25 + 63 - (10 + 83 - 38 - 53) = 88
66 - 58 - 31 + 25 - 7 + 7 + 25 + 63 - 10 + 83 - (38 - 53) = 178
------------------
66 - (58 - 31) + 25 - 7 + 7 + 25 + 63 - 10 + 83 - (38 - 53) = 240

E.g. 50-operand problem solution:

28 - (97 + 53 - 55 + 11 - 65) + 74 + 9 + 42 + 14 + 52 + 89
   - (7 - 81 - 35 - 42 - 54 + 30 + 17 - 61 + 38 - 49 + 27 - 92)
   + 55 - (49 - 8) + 65 - (23 - 68 - 72 + 30 - 63) + 85 + 38
   - (18 + 11 - 22) + 40 + 86 - (9 - 85) + 33 + 83 - (64 - 9)
   + 36 - (22 - 70) + 45
= 1299

#include <iostream>
#include <limits>
#include <random>
#include <sstream>
#include <vector>

bool verbose = false;
constexpr auto NullValue = std::numeric_limits<int>::min();
using Problem = std::vector<int>;
using Parens = std::vector<std::pair<int,int>>;

// Convert string input to vector<int>.
Problem read(std::string str) {
    std::istringstream iss(str);
    int n;
    iss >> n;
    Problem prob;
    prob.push_back(n);
    for (char op; iss >> op >> n; )
        prob.push_back(op == '-' ? -n : n);
    return prob;
}

// Generate a random input problem in vector<int> form.
// Length is from min_size to max_size; operands are from -99 to 99 (but not 0)
Problem rnd_prob(int min_size, int max_size) {
    using UID = std::uniform_int_distribution<>;
    static auto rng = std::mt19937(std::random_device{}());
    static UID distSize(min_size, max_size);
    static UID distValuesFirst(1, 99);
    static UID distValues(-98, 99);
    int size = distSize(rng);
    Problem prob;
    prob.push_back(distValuesFirst(rng)); // first must be positive
    for (int i = 1; i < size; i++) {
        int n = distValues(rng);
        if (n <= 0) --n;                  // exclude zero
        prob.push_back(n);
    }
    return prob;
}

// Calculate value given problem and parens.
int calc(Problem& prob, Parens& parens) {
    int val = 0, subval = 0, p = 0;
    bool in_group = false;
    for (int i = 0; i < int(prob.size()); ++i) {
        if (p < int(parens.size()) && parens[p].first == i && prob[i] < 0) {
            in_group = true;
            subval -= prob[i];
        }
        else if (in_group)
            subval += prob[i];
        else
            val += prob[i];
        if (p < int(parens.size()) && parens[p].second == i) {
            ++p;
            if (in_group) {
                in_group = false;
                val -= subval;
                subval = 0;
            }
        }
    }
    return val;
}

// Print problem given problem and parens vectors.
void print(Problem& prob, Parens& parens, int value=NullValue) {
    int p = 0;
    if (p < int(parens.size()) && parens[p].first == 0)
        std::cout << '(';
    std::cout << prob[0];
    for (int i = 1; i < int(prob.size()); ++i) {
        int n = prob[i];
        if (n < 0) {
            std::cout << " - ";
            n = -n;
        }
        else
            std::cout << " + ";
        if (p < int(parens.size()) && parens[p].first == i)
            std::cout << '(';
        std::cout << n;
        if (p < int(parens.size()) && parens[p].second == i) {
            std::cout << ')';
            ++p;
        }
    }
    if (value != NullValue) std::cout << " = " << value;
    std::cout << '\n';
}

// Recursive part of brute-force solver.
void brute_r(Problem& prob, Parens& parens, int &max_val,
             Parens& best_parens, int start=0) {
    for (int i = start; i < int(prob.size()); i++) {
        if (prob[i] >= 0) continue; // don't start a group on a positive
        if (i > start && prob[i-1] < 0) // don't exclude a previous negative
            continue;
        for (int j = i+1; j < int(prob.size()); j++) {
            if (prob[j] >= 0) continue; // don't end a group on a positive
            if (j<int(prob.size()-1) && prob[j+1] < 0)
                continue; // if next is also negative, include it
            parens.push_back(std::make_pair(i, j));
            int val = calc(prob, parens);
            if (verbose) print(prob, parens, val);
            if (val > max_val) {
                max_val = val;
                best_parens = parens;
            }
            brute_r(prob, parens, max_val, best_parens, j+1);
            parens.pop_back();
        }
    }
}

// Brute force solver.
int brute(Problem& prob) {
    Parens parens, best_parens;
    int max_val = calc(prob, parens); // value with no parens
    if (verbose) print(prob, parens, max_val);
    brute_r(prob, parens, max_val, best_parens);
    if (verbose) std::cout << "------------------\n";
    print(prob, best_parens, max_val);
    return max_val;
}

#include <cstdlib> // atoi
#include <cstring> // strchr

int main(int argc, char **argv) {
    int num_probs = 1, min_size = 10, max_size = 20;
    bool do_prob_string = false;
    if (argc > 1 && argv[1][0] == 'v' && argv[1][1] == '\0') {
        verbose = true;
        --argc;
        ++argv;
    }
    if (argc == 4) {
        num_probs = std::atoi(argv[1]);
        min_size = std::atoi(argv[2]);
        max_size = std::atoi(argv[3]);
    }
    else if (argc == 2) {
        if (std::strchr(argv[1], '+') || std::strchr(argv[1], '-'))
            do_prob_string = true;
        else
            min_size = max_size = std::atoi(argv[1]);
    }
    else if (argc != 1) {
        std::cerr << "Usage: brute [v] [prob_size]\n"
                     "       brute [v] num_probs min_size max_size\n"
                     "       brute [v] problem_string\n";
        return 1;
    }
    for (int i = 0; i < num_probs; i++) {
        Problem prob;
        if (do_prob_string)
            prob = read(argv[1]);
        else
            prob = rnd_prob(min_size, max_size);
        brute(prob);
        std::cout << '\n';
    }
}

[helios]

Should have converted to RPN. The search can then be made non-recursive.

[tpb]

@helios, I didn't consider RPN. The recursion in my code is just for placing multiple groups of non-nested parens. The calc routine doesn't recurse at all. I've only thought about it for a few minutes but I don't see it helping that much.

For 5 operands, using letters for operands and symbols for operators, the two forms for all non-nested parens (except for ones starting at the beginning) are

a @  b #  c  $  d  % e     a b @ c # d $ e %
a @ (b #  c) $  d  % e     a b c # @ d $ e %
a @ (b #  c  $  d) % e     a b c # d $ @ e %
a @ (b #  c  $  d  % e)    a b c # d $ e % @
a @ (b #  c) $ (d  % e)    a b c # @ d e % $
a @  b # (c  $  d) % e     a b @ c d $ # e %
a @  b # (c  $  d  % e)    a b @ c d $ e % #
a @  b #  c  $ (d  % e)    a b @ c # d e % $

The RPN version looks harder to generate to me.

Also, I am pruning the search space somewhat. Groups only start after a minus sign (that's why it can't start at the beginning), they never leave out a consecutive subtracted term, and always end on a subtracted term. E.g.,

1 - 2 - 3 - 4
(1 - 2) - 3 - 4    pointless to start on an added term
1 - (2 - 3) - 4    not considered (why leave - 4 out?)
1 - 2 - (3 - 4)    not considered (why leave - 2 out? It's subtracted anyway,
                   so may as well include it and cause the 3 to be added)