By BigBadBully, history, 9 months ago,

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):

• -36

 » 9 months ago, # |   +5 Why did i get downvotes im not wrong
 » 9 months ago, # | ← Rev. 2 →   0 Take $prod(l, r)$ as a function that calculates the product of all integers $a[l..r]$. If $prod(a, c) \geq prod(b, c)$ and $a[c] < 0$ then it's pretty obvious that your claim is incorrect. So not every function behaves like that and you have to think for every case.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 No, I said that this works for every function for which $f(a,c) \ge f(b,c) \implies f(a,c+1) \ge f(b,c+1)$. I didnt say this works for every function. I'm sorry if the title clickbaited you
•  » » » 9 months ago, # ^ |   0 I see. I hope this idea will help you in solving problems.
•  » » » » 9 months ago, # ^ |   0 I hope it helps u too :)
 » 9 months ago, # |   0 Auto comment: topic has been updated by BigBadBully (previous revision, new revision, compare).
 » 9 months ago, # |   0 Stop downvoting me
•  » » 4 months ago, # ^ |   0 why you care about contribution?
•  » » » 4 months ago, # ^ |   0 cuz if my contribvution is low that means im hated among the masses
•  » » » » 4 months ago, # ^ |   0 no
•  » » » » » 4 months ago, # ^ |   0 codeforces indeed hates me :pensiev:
•  » » » » » » 4 months ago, # ^ |   0 Honestly deserved ngl
•  » » » » » » » 4 months ago, # ^ |   0 No