Optimal way to find maximal sum (with constraints) of array elements

Question

Problem: Find the maximum sum of the elements in an array, with the following constraints:

• all the elements of the array are non-negative integers
• each element can either be left out completely from the sum (skipped), can be added, or can be subtracted from the sum
• when reading the array left to right (i.e. from index 0 to index size - 1), the sequence of operations must be subtract, add, subtract, add, ... etc, with optional skips in between (e.g. subtract, skip, skip, add, subtract, skip, add)
• in other words: the first element included in the sum must be subtracted, the next element included into the sum must be added, the next subtracted, etc... (i.e. we always start with subtraction).

Example: Suppose we have the following array: [1, 2, 3, 4, 5].

Then the sums following is valid:

-1 + 2 -3 +4 -5

-1 + 0 + 3 -4 +5

-1 + 0 + 0 + 0 + 0

0 -2 + 0 + 0 + 5

0 + 0 + 0 + 0 -5

0 + 0 + 0 + 0 + 0

Some invalid sums:

+1 -2 +3 -4 +5 // We did not start with subtraction (+1)

-1 -2 +3 -4 +5 // Two consecutive subtractions (-1 -2)

-1 +2 +0 +4 -5 // Two consecutive additions (+2 +4).

My solution: There are 2^N possible valid sums (where N is the size of the array), since if we read the array left to right, each element can either be included into the sum or not. For each of these cases, let's calculate the sum that we get, and choose the minimum of those sums.

Pseudo code of my solution:

func findMax(a []) {
    max := 0;
    for (i := 0; i < 2 ^ a.size; ++i) {
        code := i;       // binary representation of the next possibility
                        // 0: we do nothing
                        // 1: we add or remove the next element
        sum := 0;
        sign := -1;
        for (j := 0; j < a.size; ++j) {
            if (code[j] == 1) {    // jth digit of code
                sum := sum + sign * a[j];
                // if (sum < 0) { goto end } // (1) would this help?
                sign := -sign;
            }
        }
        if (sum > max) {
            max = sum;
        }
end:
    }
    return max;
}

Optimization This solution has exponential run-time complexity in the size of the array, therefore I was asking myself how to optimize it. The only idea I have is to backtrack (i.e., don't continue the calculation for a given case), whenever the partial sum becomes negative (see commented out line (1) in the pseudo code). However, I'm not sure that a.) this could not weed out in some way the maximum we are looking for (although I can't think of any counter examples) and b.) that there other, even more efficient ways to backtrack.

Questions

1.) Is there an example, where back-tracking upon encountering a negative partial sum (i.e. the solution suggested at line (1)) would prevent us from finding the real maximum sum?

2.) Is there some even better way to back-track?

3.) What other approaches exist for this problem?

Answer 1

This is a classic Dynamic Programming problem. Basically, dynamic programming is a way of turning a recursive algorithm into an iterative one with better runtime, by saving previous results that we might need again.

In this case, we can write the problem as two recursive functions:

maxSumSubtractFirst(startIndex):
    if startIndex is past the end of the array:
        return 0
    return max( # Two options: take whichever is better
        -A[startIndex] + maxSumAddFirst(startIndex+1), # Use this one
        maxSumSubtractFirst(startIndex+1) # Skip this one
    )

maxSumAddFirst(startIndex):
    if startIndex is past the end of the array:
        return 0
    return max( # Same as above
        A[startIndex] + maxSumSubtractFirst(startIndex+1),
        maxSumAddFirst(startIndex+1)
    )

In other words, we have two choices for each element: either include it (and flip the sign for the next one), or skip it (and keep the sign the same).

Now, we could run maxSumSubtractFirst(0) and get the answer that way, but this could take $O(2^n)$ in the worst case. We can do better.

Since each function will always return the same output given the same input, we can make two arrays the same length as our input, then store the results of maxSumSubtractFirst in one, and maxSumAddFirst in the other. If we start from the end (the largest index) and work backward, we'll never have to recurse at all: just look up the results in the array, which takes $O(1)$.

Now we can take the first element in the maxSumSubtractFirst array, and that's our answer. We've only had to call each function $n$ times, and each call takes $O(1)$, so this version of the algorithm runs in $O(n)$—a significant improvement over $O(2^n)$!

(Note that, as written, this only gets you the value of the sum, not the sequence of choices that led to it. But that's easy to change: make additional arrays to hold the choices, and fill them in with each call to maxSum*First.)