Q:

Why does this greedy algorithm work?

Here's the problem:

Given a sequence s of + and - characters which represent +1 and -1 operations respectively on a variable x with initial value 0, find the maximum range of values x can achieve with any subsequence of s.

Example:

s = +--+--+, x = 0
Subsequence that would lead to the maximum range of 4 is +----+. x would have max value 1 and min value -3.

The solution for this algorithm in pseudo-code is as follows:
count_minus = #occurrences of - character
count_plus = #occurences of + character
return max(count_minus, count_plus)

Why does this work?

A:

If you remove all the positives then you have max=0 and min=-#negatives for range=#negatives. Similarly for removing the negatives. Can't really get any better.

