Maximum Subarray Sum: 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 subarray?

In other words, the 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 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:

What is the Maximum Subarray Problem?

Now that we have understood what a subarray is, let us understand the Maximum Subarray problem.

In this problem, we have to find the sum which is the maximum of all the sums possible of the contiguous subarrays of the given array. Let us understand this by an example.

Let us take a sample array to be {-1,2,-3,4,7,-5}.

Now, there are multiple subarrays for this array listed below:

• {-1}
• {-1,2}
• {-1,2,-3}
• {-1,2,-3,4}
• {-1,2,-3,4,7}
• {-1,2,-3,4,7,-5}
• {2}
• {2,-3}
• {2,-3,4}
• {2,-3,4,7}
• {2,-3,4,7,-5}
• {-3}
• {-3,4}
• {-3,4,7}
• {-3,4,7,-5}
• {4}
• {4,7}
• {4,7,-5}
• {7}
• {7,-5}
• {-5}

All these are the possible subarrays for this array.

Now the sums of all these subarrays are:- -1, 1, -2, 2, 9, 4, 2, -1, 3, 10, 5, -3, 1, 8, 3, 4, 11, 6, 7, 2, -5 respectively. We can see that 11 is the maximum sum of all thus this is our result.

What is Kadane's Algorithm?

Kadane's Algorithm is an iterative dynamic programming algorithm which means it is a method that is most used to solve finite-dimensional nonlinear constrained global optimal control problems. So, to understand Kadane's Algorithm, we are required to understand Dynamic Programming first. We use Kadane's Algorithm to solve the famous problem - Maximum Subarray Sum. This Algorithm is used for solving the problem in linear time.

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 temp and final_ans, respectively. 
   
• We will initialise temp to 0 and final_ans to INT_MIN.
   
• Each time we get a positive sum, we compare it with final_ans and update final_ans if it is greater than it.
   

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

1. Start
    
2. final_ans = INT_MIN
    
3. temp = 0
    
4. Loop for each element of the array
   
   
   1. if(temp < 0)
      1. temp =  arr[i]
          
   2. else temp = temp + arr[i]
       
   3. if(final_ans < temp)
      1. final_ans = temp
          
5. return final_ans 
    

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. 

At the end of all the iterations, the value of final_ans = 11.

Therefore, the maximum contiguous subarray sum is 11.

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.

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

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

int main()
{
int arr[] = {-1,2,-3,4,7,-5};

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];
            }
            // storing sum in a vector
            v1.push_back(temp_sum);
        }
}

// 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: -1 1 -2 2 9 4 2 -1 3 10 5 -3 1 8 3 4 11 6 7 2 -5
Maximum Sum Contiguous Subarray = 11

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.

Implementation of Kadane's Algorithm

Next let us look at the implementation of Kadane's algorithm in C, C++, and Java programs. This will help you understand the algorithm better.

C Implementation of Kadane's Algorithm

The code given below uses Kadane's Algorithm for finding the maximum subarray sum for the array shown above in C language.

#include <stdio.h>

// 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 final_ans = INT_MIN;
   // Stores the maximum sum of subarray ending at the current position
   int curr = 0;
   
   // Traverse the given array
   for (int i = 0; i < n; i++) {
   // if maximum sum is negative, set it to current element's value
       if(curr < 0)
     	{
         	curr = arr[i];
     	}
     	// else add it with the current element's value
     	else curr = curr + arr[i];
     	
     	// update result if current subarray sum is found to be greater
     	if(final_ans < curr)
     	{
         final_ans = curr;    
     	}
   }
   return final_ans;
}

int main() {
   int arr[] = {-1,2,-3,4,7,-5};
   int n = sizeof(arr) / sizeof(arr[0]);
   printf("The maximum sum of a contiguous subarray is %d\n", kadane(arr, n));
   return 0;
}

Output

The maximum sum of a contiguous subarray is 11

Here, we can see that we iterate the elements linearly. We check if the current sum is negative. If it is found negative we initialize it to be the current element's value, else we add the current element to the current sum. We update the final sum if it is greater than the previous one. Finally, we return the maximum sum of a contiguous subarray found.

Java Implementation of Kadane's Algorithm

The code given below uses Kadane's Algorithm for finding the maximum subarray sum for the array shown above in Java language.

public class KadaneAlgorithm {
    // Function to find maximum sum contiguous subarray in a given set of integers
    public static int kadane(int[] arr, int n) {
        // Stores maximum sum subarray found so far
        int final_ans = Integer.MIN_VALUE;
        // Stores the maximum sum of subarray ending at the current position
        int curr = 0;

        // Traverse the given array
        for (int i = 0; i < n; i++) {
            // if maximum sum is negative, set it to current element's value
            if (curr < 0) {
                curr = arr[i];
            }
            // else add it with the current element's value
            else {
                curr = curr + arr[i];
            }

            // update result if current subarray sum is found to be greater
            if (final_ans < curr) {
                final_ans = curr;
            }
        }
        return final_ans;
    }

    public static void main(String[] args) {
        int[] arr = {-1, 2, -3, 4, 7, -5};
        int n = arr.length;
        System.out.println("The maximum sum of a contiguous subarray is " + kadane(arr, n));
    }
}

Output

The maximum sum of a contiguous subarray is 11

Here also the same approach is followed. Because we are programming it in Java language, we make a class named KadaneAlgorithm. Inside that class, we have the Kadane method to compute the final result.

C++ Implementation of Kadane's Algorithm

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

#include<iostream>
#include<climits>
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 final_ans = INT_MIN;
   
   // Stores the maximum sum of subarray ending at the current position
   int curr = 0;
   
   // Traverse the given array
   for (int i = 0; i < n; i++) {
   // if maximum sum is negative, set it to current element's value
       if(curr < 0)
     	{
         	curr = arr[i];
     	}
     	// else add it with the current element's value
     	else curr = curr + arr[i];
     	
     	// update result if current subarray sum is found to be greater
     	if(final_ans < curr)
     	{
         final_ans = curr;    
     	}
   }
   return final_ans;
}

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

Output

Maximum sum contiguous subarray is 11

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 solving the same problem. 

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

Also Read - Time Complexity of Sorting Algorithms

Advantages of Kadane's Algorithm

Some of the advantages of Kadane's Algorithm are as follows:

• Simplicity: Kadane's Algorithm is comparatively easy to implement and understand from other algorithms for solving the maximum subarray problem, such as the divide-and-conquer algorithm
• Space Complexity: This Algorithm has O(1) of space complexity, which means it uses a constant amount of memory despite the size of the input array
• Efficiency: Kadane's Algorithm has an O(n) complexity, which makes it very efficient for solving the maximum subarray problem. This makes it a great solution for big datasets
• Dynamic Programming: This Algorithm is a great example of dynamic programming. Dynamic programming is a technique that breaks down a problem into smaller subproblems and stores the solutions to these subproblems to avoid redundant computation

Disadvantages of Kadane's Algorithm

Some of the disadvantages of kadane's Algorithm are as follows:

• Only finds the sum and not the subarray: This Algorithm only finds the maximum sum of the subarray and not the actual subarray. If we want to find the subarray that has the maximum sum, we are required to modify the algorithm accordingly.
• Not suitable for non-contiguous subarrays: This Algorithm is specifically designed for contiguous subarrays and is not suitable for non-contiguous subarrays problems.
• Does not handle negative value well: If the input contains only negative value, the algorithm returns the maximum negative number instead of 0. 

Frequently Asked Questions

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 array. It operates in O(n) time complexity and O(1) space complexity. 

What is the runtime of Kadane’s algorithm?

Kadane's algorithm has O(n) run time. where n is the length of the input array. It is a linear-time algorithm that processes each array element only once and is efficient for large inputs.

What is Kadane's algorithm for maximum product?

Kadane’s algorithm for maximum product is an iterative dynamic programming algorithm in which we search for a maximum product contiguous subarray within a one-dimensional array. Here also keep the basic understanding of Kadane's algorithm to traverse the elements linearly and keep the maximum of the current product and result product as the result.

What is Kadane's algorithm for negative numbers?

For the implementation of Kadane's algorithm, at least one positive number should be present for the final sum. But in cases where all the numbers are negative, we must output the least negative one.

Conclusion

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.

Related Links -

• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Design and Analysis of Algorithms