AlgoDaily - Kadane's Algorithm Explained

Home > Data Structures and Algorithms 🚀 > Dynamic Programming Interview Questions > Kadane's Algorithm Explained

Kadane's Algorithm is a powerful technique used to solve the Maximum Subarray Problem. This tutorial is designed to guide you step-by-step through understanding the problem, exploring different solutions, and finally, mastering Kadane's Algorithm itself. Here's what we'll cover:

1. Kadane's Algorithm Overview

What Is It? Introduction to Kadane's Algorithm, its applications, and where it fits within the realm of algorithms.
Why Use It? A glimpse into why Kadane's Algorithm is preferred for solving specific problems.

2. The Maximum Subarray Problem

Definition: Understanding the problem statement and what constitutes a subarray.
Example: Illustrative examples to visualize the problem.

3. Brute Force Solution

Approach: Exploring a naive approach to solve the problem by examining all possible subarrays.
Time Complexity: Analyzing the efficiency of the brute force solution.

4. Implementation of Brute Force Solution

We'll delve into code and translate our brute force approach in popular programming languages.

5. An Optimal Solution through Kadane's Algorithm

Idea: Introduction to the logic behind Kadane's Algorithm.
Steps: Breaking down the algorithm into a sequence of comprehensible steps.
Time Complexity: Analyzing why Kadane's Algorithm is more efficient than the brute force approach.

6. Implementation of Kadane's Algorithm

We'll take our understanding of Kadane's Algorithm and turn it into code.

By the end of this tutorial, you'll not only have a clear understanding of the Maximum Subarray Problem but also be proficient in solving it using both brute force and Kadane's Algorithm.

Let's dive into the intriguing world of Kadane's Algorithm and explore how it provides an optimal solution to the Maximum Subarray Problem. We'll go through the key aspects, the problem it solves, and why it's an important method in the field of computer science.

Joseph Born Kadane and His Contribution

Joseph Born Kadane, a renowned statistician, is known for his early support of Bayesian statistics. He introduced Kadane's Algorithm at a seminar at Carnegie Mellon University. But what's so special about this algorithm? Let's delve into it.

The Problem: Maximum Subarray

The algorithm addresses a well-known problem in computer science called the Maximum Subarray Problem. Imagine having an array of integers, and you need to find a contiguous subarray that has the maximum sum. Sounds challenging, right? Here's where Kadane's Algorithm shines!

Dynamic Programming: Breaking It Down

Kadane's Algorithm falls under the category of Dynamic Programming. It's like solving a complex puzzle by breaking it down into smaller pieces:

Solve a Subproblem: Work on a small part of the problem.
Save the Solution: Keep the solution of that part in memory.
Reuse the Solution: If the same subproblem occurs, use the saved solution instead of solving it again.

This approach ensures efficiency and speed, as it avoids redundant computations.

How Kadane's Algorithm Works

Initialize Two Variables: One for the current sum (currentSum) and another for the maximum sum found so far (maxSum).
Iterate Through the Array: For each element, calculate the currentSum by adding the element to the previous currentSum. If the currentSum becomes negative, reset it to zero.
Update maxSum: If the currentSum is greater than maxSum, update maxSum.
Result: The value in maxSum is the maximum sum of a contiguous subarray.

Maximum Subarray Problem

Given an input array of size n, the Maximum Subarray Problem is to find the largest sum of a contiguous subarray within that input array. Let's understand this through an example:

In the above example, we can see that the largest sum of a contiguous subarray in the input array of size 7 is 11. Now how can we find this programmatically?

Let's dive deep into finding a solution to this problem!

Assumptions

There are no empty subarrays within the input array.
globalMaxSum denotes the largest sum of a contiguous subarray in an input array.
localMaxSum at index i denotes the largest sum of the subarrays starting with the element at input[i].
n is the size of the input array.

Brute Force Approach

The simplest solution to the problem is using the Brute Force approach:

Find all the possible contiguous subarrays.
Calculate their sum.
Find the maximum of all the sums.

Now going back to our input array to understand the Brute Force solution to the problem:

In the above example, we can see that we'll have to calculate the sum of all the possible contiguous subarrays starting at index 0 to n-1. The above illustration is for index 0. The same step will be repeated for all the indices. Let's understand this solution to find the globalMaxSum:

This approach will require two loops.
An outer loop with index i that will iterate from 0 to n-1.
An inner loop with index j that will iterate from j set to i to n-1.
The inner loop will calculate subArraySum:

SNIPPET

1subArraySum = subArraySum + input[j]

Meanwhile, subArraySum will be compared with globalMaxSum.
If globalMaxSum will be less than subArraySum, then globalMaxSum will be set to subArraySum.
In the end, we'll be able to find out the largest sum of a contiguous subarray.
Note that the time complexity for this algorithm is O(n²)

Now heading to implementation in code to get a clearer understanding:

xxxxxxxxxx
 
function solveMaxSubArrayProblem(input)
{
    var n = input.length
    var globalMaxSum = Number.MIN_VALUE
    var subArraySum
      
        for (var i = 0; i < n ; i++) {
            subArraySum= 0;
            for (var j = i; j < n; j++) {
            subArraySum+= input[j]
            if (subArraySum> globalMaxSum) {
                globalMaxSum = subArraySum
            }
            }
        }
    return globalMaxSum
}
  
var input = [ 1, -2, 5, -3, 4, -1, 6 ]
var result = solveMaxSubArrayProblem(input)
document.write(result)

Are you sure you're getting this? Click the correct answer from the options.

What is the time complexity to find the largest sum of a contiguous subarray using the Brute Force Approach?

Click the option that best answers the question.

O(n)
O(1)
O(log n)
None of the above

Kadane's Algorithm - Unpacking an Optimal Solution

To thoroughly understand Kadane's Algorithm, we'll examine an example array: [1, -2, 5, -3, 4, -1, 6]. Here's an illustrative representation:

Introducing the Concept of "localMaxSum"

The key concept in Kadane's Algorithm is "localMaxSum," which represents the maximum sum of a contiguous subarray ending at a specific index. By keeping track of this "local" maximum, we can efficiently find the "global" maximum sum across the entire array.

Exploring localMaxSum[3]

Why are we looking at localMaxSum[3]? It's a pivotal point in understanding the algorithm. By examining this specific index, we can gain insights into how the algorithm builds solutions progressively. Let's break it down:

Possible Contiguous Subarrays

A "contiguous subarray" means a continuous sequence of elements within the array. For localMaxSum[3], the possible contiguous subarrays are:

[-3] // index 3 only
[5,-3] // index 2 & 3
[-2,5,-3] // index 1, 2 & 3
[1,-2,5,-3] // index 0, 1, 2 & 3

These combinations represent different ways to sum the elements ending at index 3. Among these, the combination [5,-3] sums up to 2, and therefore, the localMaxSum[3] is found to be 2.

An Insightful Observation

Now, let's compare localMaxSum[3] with localMaxSum[2]. What distinguishes them? It's only the element -3 at index 3. To find localMaxSum[3], we need the previous localMaxSum[2] and the element at index 3.

The Insight's Significance

This observation forms the heart of Kadane's Algorithm. It tells us that the localMaxSum at index i depends on only two factors: 1. The current element at index i. 2. The localMaxSum at the previous index i-1.

This relationship simplifies the problem significantly and leads to an efficient solution.

Implementing Kadane's Algorithm

Now, let's translate our understanding into practical steps and code:

Loop Through the Array: Iterate from index 0 to n-1.

Calculate localMaxSum: Use the formula:

SNIPPET

1localMaxSum[i] = max(input[i], input[i] + localMaxSum[i-1])

Compare with globalMaxSum: If localMaxSum is greater, update globalMaxSum.
Result: The largest sum of a contiguous subarray is in globalMaxSum.
Efficiency: The time complexity is O(n).

xxxxxxxxxx
 
function solveMaxSubArrayProblem(input)
{
    var n = input.length
    var globalMaxSum = Number.MIN_VALUE
    var localMaxSum = 0
      
        for (var i = 0; i < n ; i++) {
            localMaxSum = Math.max(input[i],input[i]+localMaxSum)
            if(localMaxSum>globalMaxSum){
                globalMaxSum = localMaxSum
            }
​
        }
    return globalMaxSum
}
  
var input = [ 1, -2, 5, -3, 4, -1, 6 ]
var result = solveMaxSubArrayProblem(input)
document.write(result)

Are you sure you're getting this? Click the correct answer from the options.

What is the time complexity to find the largest sum of a contiguous subarray using Kadene's algorithm?

Click the option that best answers the question.

O(n)
O(1)
O(log n)
None of the above

Conclusion: Mastering the Maximum Subarray Problem

In this enlightening journey, we delved into solving the Maximum Subarray Problem using the powerful Kadane's Algorithm. Here's a recap of what we covered:

Understanding the Problem

We started by unraveling a common challenge in computer science: finding the largest sum of contiguous elements in an array. It's a problem that might seem simple at first glance but holds fascinating complexity.

Introducing Kadane's Algorithm

Named after Joseph Born Kadane, this algorithm offers an optimal and elegant solution to the problem. Its beauty lies in the way it breaks down the complex task into manageable steps.

Exploring the Concept of "localMaxSum"

We focused on the essential concept of "localMaxSum," representing the maximum sum of a contiguous subarray ending at each specific index. By understanding how each local maximum builds upon the previous one, we discovered the algorithm's efficiency.

Insightful Observations

We took a deep dive into localMaxSum[3], uncovering how the algorithm builds solutions incrementally. This led to valuable insights, revealing a simple yet powerful relationship between consecutive local maximum sums and laying the groundwork for an optimal solution.

Implementing the Algorithm

We translated our understanding into practical code implementations across multiple programming languages. This hands-on approach provided a clear path to applying Kadane's Algorithm in real-world scenarios.

The Power of Incremental Solutions

Kadane's Algorithm is a shining example of how focusing on local, incremental solutions can lead to a global understanding. By solving small parts of the problem and building upon them, it offers an efficient and mathematically elegant approach.

One Pager Cheat Sheet

We're going to learn about Kadane's Algorithm and its implementation in Python, JavaScript, and Java, in order to solve the Maximum Subarray Problem.
Kadane's Algorithm is a form of Dynamic Programming developed by Joseph Born Kadane which provides an optimal solution for the Maximum Subarray Problem.
The Maximum Subarray Problem is to find the largest sum of a contiguous subarray in an input array of size n.
The Brute Force approach can be used to calculate the largest sum of a contiguous subarray in an array by comparing all possible subarrays and setting the max sum to a globalMaxSum variable, with a time complexity of O(n^2).
The time complexity of this algorithm is O(n²), as it requires two loops (outer loop with index i from 0 to n-1 and inner loop with index j from j set to i to n-1).
Kadene's Algorithm is an optimal approach with time complexity O(n), to the maximum subarray problem which is found by looping through the array, comparing the local Max Sums, and updating the global Max Sum at each iteration.
Kadene's Algorithm to find the largest sum of a contiguous subarray has a time complexity of O(n) due to its single loop iteration from index 0 to index n-1.
We solved the Maximum Subarray Problem in an optimal way using Kadene's Algorithm.

1. Kadane's Algorithm Overview

2. The Maximum Subarray Problem

3. Brute Force Solution

4. Implementation of Brute Force Solution

5. An Optimal Solution through Kadane's Algorithm

6. Implementation of Kadane's Algorithm

Joseph Born Kadane and His Contribution

The Problem: Maximum Subarray

Dynamic Programming: Breaking It Down

How Kadane's Algorithm Works

Maximum Subarray Problem

Assumptions

Brute Force Approach

Are you sure you're getting this? Click the correct answer from the options.

Click the option that best answers the question.

Kadane's Algorithm - Unpacking an Optimal Solution

Introducing the Concept of "localMaxSum"

Exploring localMaxSum[3]

Possible Contiguous Subarrays

An Insightful Observation

The Insight's Significance

Implementing Kadane's Algorithm

Are you sure you're getting this? Click the correct answer from the options.

Click the option that best answers the question.

Conclusion: Mastering the Maximum Subarray Problem

Understanding the Problem

Introducing Kadane's Algorithm

Exploring the Concept of "localMaxSum"

Insightful Observations

Implementing the Algorithm

The Power of Incremental Solutions

One Pager Cheat Sheet

Programming Categories

Popular Lessons