DEV Community

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

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

QuanticDev
QuanticDev. Senior software engineer and the developer of several popular projects.
・1 min read

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)

Forem Open with the Forem app