Algorithm for minimum sum subvector

Question

The problem found in programming pearls column 8 is as follows:

Given the real vector x[n], compute the maximum sum found in any contiguous subvector.

The final solution provided is of O(n) complexity which is as follows:

std::vector<int> x;
int max_so_far = 0;
int max_here = 0;
for (std::size_t i = 0; i < x.size(); ++i)
{
   max_here = std::max(max_here + x[i], 0);
   max_so_far = std::max(max_so_far, max_here);
}

I would like to know how does one go about modifing the above algorithm to provide the minimum sum.

Answer 1

You only need to invert the sign of each element in x and then run the algorithm:

std::vector<int> x;
int max_so_far = 0;
int max_here = 0;

for (std::size_t i = 0; i < x.size(); ++i) x[i] = -x[i];

for (std::size_t i = 0; i < x.size(); ++i)
{
   max_here = std::max(max_here + x[i], 0);
   max_so_far = std::max(max_so_far, max_here);
}

int min_so_far = -max_so_far;