QuanticDev

QuanticDev's Engineering and Software Development Resources

Home Shop View on GitHub

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

In this article, you will get the optimum solution to the maximum/minimum sum subarray problem: The Kadane’s Algorithm. The problem at hand is simple. Given an array of integers, say [-1, 1, 3, -2], find the subarrays with the maximum and minimum possible sums (for the given example: max=[1, 3], min=[-2]). Kadane’s Algorithm solves this problem with a nice O(n) time and O(1) space complexity. A variation of this problem is when you are trying to find the maximum/minimum sum subarray with at least k elements. Again, a slightly modified version of Kadane’s Algo can be used in solving it. Finally, we will prove the correctness of Kadane’s Algorithms.

In the article, you will find the solutions to the following questions, as well as their time and space complexities:

Resources

You can find the video narration of this article on YouTube: https://www.youtube.com/watch?v=4csAswCkXZM

Video has additional tips and illustrations. If you want to read the comments or leave a comment, do so under YouTube video. If you want to contribute to the article, make a pull request on GitHub.

Overview

When all integers in a given array are positive, you can use the much simpler Sliding Windows Technique. For arrays with negative numbers, you can modify it to be all positive numbers and then apply the sliding window technique, but that requires extra processing; hence it is not the optimum solution. I have a separate article discussing the sliding window technique in depth along with various sample questions, and you can find the link to it above.

Kadane’s Algorithm uses optimal substructures to solve the max/min subarray sum problem. Each max/min subarray ending at each index is calculated using the max/min subarray ending at the previous index. You can say that this is an accumulation function with some additional rules. As a result of this, it is one of my favorite examples of Dynamic Programming. In the article, I will explain how Kadane’s Algorithm is an optimal substructure problem using a basic animation.

Question #1: Medium Difficulty: Given an array of integers, find the subarray with the maximum/minimum possible sum

Example Input: [1, 2, -4, 3, 4, -2]

Requirements Analysis:

Problem Analysis:

Approach #1: Brute Force

Approach #2: Kadane’s Algorithm

How Does It Work?

Rules:

Tips!

Question #2: Medium Difficulty: Given an array of integers, find the subarray with the maximum/minimum possible sum with at least k elements

Example Input (k=3): [1, 2, -4, 3, 4, -2]

Max Sum at Each Index: [1, 3, 0, 3, 7, 5]

Solution: Sliding Window on Kadane’s Algorithm

Proof of Correctness of Kadane’s Algorithm

More Tips!

Video Solutions

If you want video solutions for the above questions, visit the YouTube link in the resources section. The video has a lot more in-depth info on solution techniques along with helpful visuals.