Kadane’s Algorithm

Introduction

If you are a competitive programmer or someone preparing for campus placements or technical interviews, you have probably come across the following question:

Given an integer array, find the contiguous subarray (containing at least one number) with the largest sum or in other words the maximum sum contiguous subarray and print its sum.

If not, does the name Kadane’s algorithm sound familiar?

It’s alright if you’re hearing this name for the first time.

You may be wondering what it is and why we need to solve the problem using Kadane’s algorithm. This article will explain what Kadane’s algorithm is and how to use it.

Before delving deeper into the concepts of Kadane’s algorithm, we must first understand what a sub-array is.

What is a sub-array?

In other words, problem statement:

An array is a contiguous memory block, as we all know. 

So, a subarray is a slice of a contiguous array that maintains the order of the elements. 

It’ll help if you remember that a sub-array may comprise a single element from the given array or the given array as a whole too.   

The diagram below shows the sub-arrays that we can form for the first two elements.

To understand this let us consider an array, 

arr = {1,2,3,4,5}

For this array, the sub-arrays are:

For element at 0th index	{1}, {1,2}, {1,2,3}, {1,2,3,4}, {1,2,3,4,5}
For element in 1st index	{2}, {2,3}, {2,3,4}, {2,3,4,5}
For element in 2nd index	{3}, {3,4}, {3,4,5}
For element in 3rd index	{4}, {4,5}
For element in 4th index	{5}

Now that we know what sub-arrays are. 

Can you come up with a brute force solution for the above problem?

Brute Force Approach

The brute force solution calculates the sum of each subarray and then compares the results to determine the maximum sum of all subarray sums.

To understand it, let us consider the following array:

The code for the brute force method would be as follows:

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
	int n = sizeof(arr)/sizeof(arr[0]);
	vector<int>v1;
	//To choose the starting point of subarray
	for(int i=0;i<n;i++)
	{
        //To choose the end point of subarray
        for(int j=i;j<n;j++)
    	{
        	int temp_sum= 0;
            //Finding the sum of the subarray
            for(int k=i;k<=j;k++)
        	{
        	    temp_sum = temp_sum + arr[k];
            }
            v1.push_back(temp_sum);// storing sum in a vector
    	}
	}
	//To print the individual subarray sum..
    cout << "Sum of individual Subarray: ";
    for (int i = 0; i < v1.size(); i++)
            cout << v1[i] << " ";
    cout << endl;
	//To print the maximum sum contiguous subarray
	cout << "Maximum Sum Contiguous Subarray = "<< *max_element(v1.begin(), v1.end());
    return 0;
}

Output:

Sum of individual Subarray: -2 -5 -1 -2 -4 -3 2 -1 -3 1 0 -2 -1 4 1 4 3 1 2 7 4 -1 -3 -2 3 0 -2 -1 4 1 1 6 3 5 2 -3Maximum Sum Contiguous Subarray = 7

This method is straightforward, but we do not use it commonly. Wondering why?

That is because it has a time complexity of O(N³) and O(N) space complexity.

As we know, while writing any program, Time and Space Complexity plays a vital role in choosing the algorithm. 

Therefore, we use Kadane’s algorithm because of its advantage considering time and space complexity.

What is Kadane’s Algorithm?

Kadane’s algorithm is an iterative dynamic programming algorithm in which we search for a maximum sum contiguous subarray within a one-dimensional numeric array.

Now, let us see how Kadane’s Algorithm works.

Working of Kadane’s Algorithm

Some of you may think it’ll be a sum of all elements in an array. But what if there will be negative integer elements in the array, which will decrease the array’s total sum.

Thus, we can see that the sum of all elements in an array isn’t always the case.

A simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array and keep track of the maximum sum contiguous subarray among all positive segments. 

• First, we will consider two elements, one which stores the maximum end of the subarray and another which stores the maximum sum so far. 
• Let these two variables be max_ending_here and max_so_far, respectively. 
• We will initialise both of them to 0. 
• Each time we get a positive sum, we compare it with max_so_far and update max_so_far if it is greater than it.

This logic is written in the form of an algorithm as follows:

1. Start
2. max_so_far = 0
3. max_ending_here = 0
4. Loop for each element of the array

1. max_ending_here = max_ending_here + a[i]
2. if(max_ending_here < 0)

max_ending_here = 0

3.     if(max_so_far < max_ending_here)

max_so_far = max_ending_here

      5.   return max_so_far 

Let us understand the working better with the same array we considered before:

Initially, max_so_far = max_ending_here = 0. i is the counter for the loop and it is also initialised with 0.

For i = 0,	max_ending_here = max_ending_here + a[i] = 0 + -2 = -2Since max_ending_here < 0, max_ending_here = 0
For i = 1,	max_ending_here = max_ending_here + a[i] = 0 + -3 = -3Since max_ending_here < 0, max_ending_here = 0
For i = 2,	max_ending_here = max_ending_here + a[i] = 0 + 4 = 4Since max_so_far < max_ending_here, max_so_far = max_ending_here = 4
For i = 3,	max_ending_here = max_ending_here + a[i] = 4 + -1 = 3
For i = 4,	max_ending_here = max_ending_here + a[i] = 3 + -2 = 1
For i = 5,	max_ending_here = max_ending_here + a[i] = 1 + 1 = 2
For i = 6,	max_ending_here = max_ending_here + a[i] = 2 + 5 = 7Since max_so_far < max_ending_here, max_so_far = max_ending_here = 7
For i = 7,	max_ending_here = max_ending_here + a[i] = 7 + -3 = 4

At the end of all the iterations, the value of max_so_far = 7.

Therefore, the maximum contiguous subarray sum is 7.

Code for Kadane’s Algorithm in C++

The code given below uses Kadane’s Algorithm to find the maximum subarray sum for the array shown above.

#include<iostream>
using namespace std;

//Function to find maximum sum contiguous subarray in a given set of integers

int kadane(int arr[], int n)
{
	//stores maximum sum subarray found so far
	 
	int max_so_far = 0;
	 
	//stores the maximum sum of subarray ending at the current position

	int max_ending_here = 0;

	//traverse the given array

	for (int i = 0; i < n; i++)
	{
    	/* update maximum sum of subarray "ending" at index i (by adding the current element to maximum sum ending at previous index i-1) */

    	max_ending_here = max_ending_here + arr[i];
 
    	/* if maximum sum is negative, set it to 0 (which represents an empty sub-array) */
    	if(max_ending_here < 0)
    	{
        	max_ending_here = 0;
    	}
     	 
    	//update result if current subarray sum is found to be greater
    	if(max_so_far < max_ending_here)
    	{
        	max_so_far = max_ending_here;    
    	}
	return max_so_far;
}

int main()
{
 	int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
 	int n = sizeof(arr)/sizeof(arr[0]);
 	cout << "Maximum sum contiguous subarray is "<<kadane(arr, n);
 	return 0;
}

Output:

Maximum sum contiguous subarray is 7

Time Complexity: O(N)

Space Complexity: O(1)

We saw that the time complexity of Kadane’s algorithm is less than that of the brute force method when it comes to solving the same problem. 

Hence, Kadane’s algorithm is our preferred method when it comes to finding the maximum contiguous subarray sum.

Special Case

The array shown in the example above has a combination of positive and negative elements, but what would happen if the array had only negative elements?

The code given below uses Kadane’s algorithm to find the maximum contiguous subarray sum in such a case.

#include<iostream>
using namespace std;

int kadane(int arr[], int n)
{
	int max_so_far = arr[0];
	int max_ending_here = arr[0];

	for (int i = 1; i < n; i++)
	{
    	if(arr[i] < (max_ending_here + arr[i]))
    	{
   		 max_ending_here = max_ending_here + arr[i];
    	}
    	else
    	{
        	max_ending_here = arr[i];
    	}
    	if(max_so_far < max_ending_here)
    	{
   		 max_so_far = max_ending_here;
    	}
	}
	return max_so_far;
}

int main()
{
	int arr[] = {-2, -3, -4, -1, -2, -1, -5, -3};
	int n = sizeof(arr)/sizeof(arr[0]);
	cout << "Maximum sum contiguous subarray is " << kadane(arr,n);
	return 0;
}

Output:

Maximum sum contiguous subarray is -1

The working of the code above is the same as that of the normal Kadane’s algorithm. The only difference is the following part:

if(arr[i] < (max_ending_here + arr[i]))

     {

    max_ending_here = max_ending_here + arr[i];

     }

     else

     {

         max_ending_here = arr[i];

     }

Here, we were previously comparing the variable “max_ending_here” with 0, but we can’t do that anymore since all the elements in the array are less than 0. So, instead, we are comparing the sum of the consecutive elements with the current element from the array. 

The time complexity will also be O(n), and space complexity will be O(1).

We recommend you to practice Maximum subarray sum on Codestudio after knowing all about its approach.

For further practice, here are a few problems that involve the idea of kadane’s algorithm:

• Flip Bits 
• Maximum Subarray Sum after K Concatenations 
• Maximum Sum Rectangle

Frequently Asked Questions

Key Takeaways

This article explains Kadane’s algorithm and how we use it to solve a common question (maximum subarray sum) in technical interviews. 

Although it appears that the solution should not be as simple as it is, but that’s the beauty of kadane’s algorithm.

There’s no need to collect loads of redundant and additional data about each possible sub-array because we optimise the answer so specifically around collecting only the information we need to know.

Knowing such a solution will help you in seeking more linear solutions to other problems. 

Apart from that, it would be best if you learned more about other top Standard Algorithms for a Coding Interview.Additionally, you can use CodeStudio to practise a wide range of DSA tasks typically asked in interview rounds. This will assist you in mastering efficient coding methodologies, with the added benefit of scholar interview experiences in large product-based organisations.

By Neelakshi Lahiri