The algorithm itself is as follows. We will go through the array and accumulate the current partial sum in some variable s. If at some point s turns out to be negative, then we simply assign s = 0. It is argued that the maximum of all values ​​of the variable s that occurred during the operation will be the answer to the problem.

We prove this algorithm.

In fact, consider the first point in time when the sum s has become negative. This means that, starting from the zero partial sum, we finally came to a negative partial sum, which means that all this array prefix, as well as any of its suffixes, have a negative sum. Consequently, there can be no further benefit from this whole array prefix: it can only give a negative increase in the answer.

However, this is not enough to prove the algorithm. In the algorithm, we, in fact, limit ourselves to finding the answer only to such segments that begin immediately after the places where s <0 happened.

But, in fact, consider an arbitrary segment [l; r], and l is not in such a “critical” position (ie, l> p + 1, where p is the last such position, in which s <0). ? ......... It is not clear here why one is added to the position p?

Further: Since the last critical position is strictly earlier than in l-1, it turns out that the sum of a [p + 1 .... l-1] is non-negative. This means that by moving l to the position p + 1, we will increase the answer or, as a last resort, do not change it. ? ......... It is not clear here why one is subtracted from l now .. And the end of the paragraph is also not clear, why move l to the position p + 1?

Further: One way or another, it turns out that when searching for an answer, one can limit oneself to segments that start right after the positions in which s <0. This proves the correctness of the algorithm. Algorithm code in C, in which I still can not understand what it means "ans"? I implement it (if I implement of course) myself in another language.

int ans = a[0], ans_l = 0, ans_r = 0, sum = 0, minus_pos = -1; for (int r=0; r<n; ++r) { sum += a[r]; if (sum > ans) { ans = sum; ans_l = minus_pos + 1; ans_r = r; } if (sum < 0) { sum = 0; minus_pos = r; } }

Why do we need a variable of the minimum position equal to -1? It’s probably easier to explain the whole code (... thank you in advance .. if you find time to chew on it ... введите сюда код

    1 answer 1

    In ans maximum value of the sum is remembered (look - its value is updated only when the sum exceeds it. At the same time, the corresponding index is stored in the ans_r . Well, minus_pos remembers, respectively, where the last time the value of the sum (including zeroing) was negative. If never had - minus_pos will have a nonexistent index value -1.