Generalization of Kadane's algorithm to functions

Revision en2, by BigBadBully, 2023-09-09 09:55:51

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 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 - Replace With Product is a good example, as well as 1796D - Maximum Subarray

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English BigBadBully 2023-09-09 19:12:49 13
en8 English BigBadBully 2023-09-09 17:32:42 49
en7 English BigBadBully 2023-09-09 17:22:40 0 (published)
en6 English BigBadBully 2023-09-09 10:52:06 116
en5 English BigBadBully 2023-09-09 09:58:31 13 Tiny change: 'ion takes array elements as param' -> 'ion takes subarray bounds as param'
en4 English 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 English 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 English BigBadBully 2023-09-09 09:55:51 2 Tiny change: 'd in the $a_{l..r}$ subarray' -> 'd in the $$a_{l..r}$$ subarray'
en1 English BigBadBully 2023-09-09 09:55:28 2398 Initial revision (saved to drafts)