Revision en9, by BigBadBully, 2023-09-09 19:12:49

I'm pretty sure a large amount of people have at the very least heard of Kadane's algorithm. It is a way to find the maximum subarray sum (of an array). But why does it work? Besides the normal proof/explanation, is there another way to explain why it is correct?

Let's fix the right boundary of the subarray. From now on, it is called $r$. Now we want to find the optimal left boundary, $l$, for every $r$. For the answer we can just find the maximum of all fixed $r$. How could we do this? Well for a given $r$ let's assume we already found the $l$. How does the answer change for $r+1$? For $r+1$, all we did was just add $a_{r+1}$ to every subarray we had so far. For every integer value $a,b,c$ it holds true that

$a \ge b \implies a + c \ge b + c$

This means that the greatest subarray sum will still be greater than every subarray whose left boundary was contained in the $a_{l..r}$ subarray, so we only need to check if the subarray sum $a_{{r+1}..{r+1}}$ (the element $a_{r+1}$) is greater than the sum of $a_{l..r+1}$. Because this is true for the $a_{1..2}$ subarray it holds true for every subarray, completing our proof by induction. Why does this prove Kadane's algorithm? Because when we consider the $a_{{r+1}..{r+1}}$ subarray, in the perspective of the $r$ before, we are considering the neutral element of addition, 0. Following the property stated beforehand, this means the answer doesn't change based on whether we evaluate $0 > a_{l..r}$ or $a_{r+1} > a_{l..r+1}$

Does this only work for subarray sums? It turns out that every function for which

$f(a,c) \ge f(b,c) \implies f(a,c+1) \ge f(b,c+1)$

holds true this works (the function takes subarray bounds as parameters). We in turn get a very simple general Kadane's algorithm. A considerable number of practical functions have this property, but I don't know of much problems that can be solved by reduction to such functions. If you want to prove that the function has the property you can also use something like I used in the proof of Kadane's subarray sum algorithm.

Besides the proof by induction I presented here is a proof by AC (if you don't believe me):

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 BigBadBully 2023-09-09 09:56:34 2 Tiny change: 'd in the ${a_{l..r}}$ subarra' -> 'd in the $a_{l..r}$ subarra'
en3 BigBadBully 2023-09-09 09:56:16 4 Tiny change: 'd in the $$a_{l..r}$$ subarray' -> 'd in the ${a_{l..r}}$ subarray'
en2 BigBadBully 2023-09-09 09:55:51 2 Tiny change: 'd in the $a_{l..r}$ subarray' -> 'd in the $$a_{l..r}$$ subarray'