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
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
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/
Why did i get downvotes im not wrong
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.
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
I see. I hope this idea will help you in solving problems.
I hope it helps u too :)
Auto comment: topic has been updated by BigBadBully (previous revision, new revision, compare).
Stop downvoting me
why you care about contribution?
cuz if my contribvution is low that means im hated among the masses
no
codeforces indeed hates me :pensiev:
Honestly deserved ngl
No