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 (
skip
ped), can be added, or can be subtracted from the sum - when reading the array left to right (i.e. from index
0
to indexsize - 1
), the sequence of operations must besubtract
,add
,subtract
,add
, ... etc, with optionalskip
s 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?