Алгоритм подсчета минимальной суммы

Question

Проблема, обнаруженная в столбце 8 программирования жемчужин, заключается в следующем:

Учитывая реальный вектор x[n], вычислите максимальную сумму, найденную в любом смежном подвекторе.

Окончательное решение имеет сложность O(n), а именно:

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);
}

Я хотел бы знать, как можно изменить вышеприведенный алгоритм, чтобы получить минимальную сумму.

Answer 1

Вам нужно только инвертировать знак каждого элемента в x и затем запустите алгоритм:

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;