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

Unable to parse markup [type=CF_MATHJAX]

(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 array elements 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/

Some other problems should also be solvable like this. 1872G - Замените на произведение is a good example, as well as 1796D - Максимальный подмассив