1.
Introduction
2.
What is a subarray?
3.
What is the Maximum Subarray Problem?
4.
5.
6.
Brute Force Approach
6.1.
C++
7.
7.1.
7.2.
C
7.3.
7.4.
Java
7.5.
7.6.
C++
8.
9.
10.
10.1.
10.2.
What is the runtime of Kadane’s algorithm?
10.3.
What is Kadane's algorithm for maximum product?
10.4.
What is Kadane's algorithm for negative numbers?
11.
Conclusion
Last Updated: Apr 17, 2024
Easy

Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

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:

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

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.

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:

• C++

C++

``#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 subarrayfor(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 subarraycout << "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(N3) 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.

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.

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

• C

C

``#include <stdio.h>// Function to find maximum sum contiguous subarray in a given set of integersint 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.

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

• Java

Java

``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.

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

• C++

C++

``#include<iostream>#include<climits>using namespace std;// Function to find maximum sum contiguous subarray in a given set of integersint 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

• 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

• 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.

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.