Maximum subarray problem: Difference between revisions

Revision as of 08:26, 25 October 2023

Revision as of 15:41, 1 December 2023

Line 48:

and easily obtained as the maximum of all values of <code>current_sum</code> seen so far, cf. line 7 of the algorithm.

As a [[loop invariant]], in the <math>j</math>th step, the old value of <code>current_sumbest_sum</code> holds the maximum over all <math>i \in \{ 1,\ldots, j-1 \}</math> of the sum <math>A[i]+\cdots+A[j-1]</math>.

Therefore, <code>current_sum</code><math>+A[j]</math>{{NoteTag|

In the Python code below, <math>A[j]</math> is expressed as <code>x</code>, with the index <math>j</math> left implicit.