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): ↵
↵
CSES Kadane's: https://cses.fi/problemset/result/7030713/ or https://cses.fi/paste/5900cd60d6a09ffc6b47b9/↵
↵
↵
↵
↵
↵
↵
↵
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): ↵
↵
CSES Kadane's: https://cses.fi/problemset/result/7030713/ or https://cses.fi/paste/5900cd60d6a09ffc6b47b9/↵
↵
↵
↵
↵
