DEV Community

Cover image for Kadane's Algorithm and Its Proof - Max/Min Sum Subarray Problem
QuanticDev
QuanticDev

Posted on

Kadane's Algorithm and Its Proof - Max/Min Sum Subarray Problem

I have previously published an article on max/min subarray sum problem using Sliding Window technique. Now it is time to one-up it with Kadane's Algorithm, which also handled arrays with negative numbers. It is slightly more complex than Sliding Windows Technique but it is a frequent ingredient of many programming interview questions. It is also a prime example of Dynamic Programming.

Discussion (0)