Do you want to solve the Maximum Sum Subarray problem in an optimized way? Today you will learn Kadane’s algorithm that lets you solve this difficult algorithm question in the most optimized and fastest way.
You’re probably trying to solve the “Maximum Subarray Problem” and ran into Kadane’s Algorithm but couldn’t figure out how it worked.
To further grasp Kadane’s Algorithm[1], we will first review Dynamic Programming. On to a well-known programming challenge, the Maximum Sum Subarray Problem. Then we would try to refine our method and come up with a better algorithm, named Kadane’s Algorithm.
Maximum Sum Subarray Problem
Write an efficient program to find the biggest sum of contiguous subarrays contained within a one-dimensional array of numbers.
Kadane’s Algorithm
Let us see the Psuedo Code below for Kadane’s Algorithm. With this, you can understand the basic flow of the algorithm and how the maximum sum subarray problem is resolved in linear time of execution.
The basic idea of Kadane’s approach is to find all positive contiguous array segments (using currentMaxValue). And maintain track of the maximum total contiguous segment (maxSumSubArray). If we have a positive sum, we compare it to the max so far and update the max so far.
Initialize:
currentMaxValue = 0
maxSumSubArray = INT_MIN
Loop for each element of the array
(a) currentMaxValue = currentMaxValue + a[i]
(b) if(maxSumSubArray < currentMaxValue)
maxSumSubArray = currentMaxValue
(c) if(currentMaxValue < 0)
currentMaxValue = 0
return maxSumSubArrayLet us see the above Psuedo Code in Real Code for Python and C++ below. The above pseudo-code and below code do not take into account that all the elements of the array will be negative or when the max sum will be or can be only negative value.
#include<bits/stdc++.h>
using namespace std;
//Calculation of Maximum Sub using Kadane's Algorithm
//Here Maximum sum is always assumed to be above zero.
int getMaxSubArraySum(vector<int> &givenArray, int size){
int maxSumSubArray = INT_MIN;
int currentMaxValue = 0;
for (int i = 0; i < size; i++)
{
currentMaxValue = currentMaxValue + givenArray[i];
if (maxSumSubArray < currentMaxValue)
maxSumSubArray = currentMaxValue;
if (currentMaxValue < 0)
currentMaxValue = 0;
}
return maxSumSubArray ;
}
/*Driver program to test Get the Maximum Sum of Contiguous Sub Array*/
int main()
{
vector<int> givenArray = {-1,1,2,2,-1,-3,-1,0,3};
int size = givenArray.size();
int maxSumSubArrayVal = getMaxSubArraySum(givenArray, size);
cout << "Maximum contiguous sum is " << maxSumSubArrayVal;
return 0;
}
# Find maximum contiguous subarray using Kadane's Algorithm
#Function Implementing the Above Psuedo Code to get
#Maximum Sum of Sub Array using Kadane's Algorithm
def getMaxSubArraySum(givenArray,size):
#Since in Python 3 we Donot have MAXINT
# Hence Negative Infinity can be represented as below
maxSumSubArray = float('-inf')
currentMaxValue = 0
for i in range(0, size):
currentMaxValue = currentMaxValue + givenArray[i]
if (maxSumSubArray < currentMaxValue):
maxSumSubArray = currentMaxValue
if currentMaxValue < 0:
currentMaxValue = 0
return maxSumSubArray
# Driver function to check the above function
givenArray = [-1,1,2,2,-1,-3,-1,0,3]
print("Maximum contiguous sum is", getMaxSubArraySum(givenArray,len(givenArray)))
Output:
Maximum contiguous sum is 5Alternative When Max Sum of Contiguous Sub Array will be Negative
An extension of the above problem can be how will you compute the maximum sum of a contiguous subarray when the maximum sum can be negative.
With little modification being made in the above code we will be able to get the sum even if the maximum sum is negative or when all the elements in the array are negative.
#include<bits/stdc++.h>
using namespace std;
//Calculation of Maximum Sub using Kadane's Algorithm
//Here Maximum sum may be negative as well.
int getMaxSubArraySum(vector<int> &givenArray, int size){
int maxSumSubArray = INT_MIN;
int currentMaxValue = 0;
for (int i = 0; i < size; i++)
{
if(givenArray[i] < givenArray[i] + currentMaxValue)
currentMaxValue += givenArray[i];
else
currentMaxValue = givenArray[i];
if(maxSumSubArray < currentMaxValue)
maxSumSubArray = currentMaxValue;
}
return maxSumSubArray ;
}
/*Driver program to test Get the Maximum Sum of Contiguous Sub Array*/
int main()
{
vector<int> givenArray = {-3,-4,-5,-20,-21,-32,-25,-15};
int size = givenArray.size();
int maxSumSubArrayVal = getMaxSubArraySum(givenArray, size);
cout << "Maximum contiguous sum is " << maxSumSubArrayVal;
return 0;
}
# Find maximum contiguous subarray using Kadane's Algorithm
#Function Implementing the Above Psuedo Code to get
#Maximum Sum of Sub Array using Kadane's Algorithm
def getMaxSubArraySum(givenArray,size):
#Since in Python 3 we Donot have MAXINT
# Hence Negative Infinity can be represented as below
maxSumSubArray = float('-inf')
currentMaxValue = 0
for i in range(0, size):
if givenArray[i] < currentMaxValue + givenArray[i]:
currentMaxValue += givenArray[i]
else:
currentMaxValue = givenArray[i]
if maxSumSubArray < currentMaxValue:
maxSumSubArray = currentMaxValue
return maxSumSubArray
# Driver function to check the above function
givenArray = [-3,-4,-5,-20,-21,-32,-25,-15]
print("Maximum contiguous sum is", getMaxSubArraySum(givenArray,len(givenArray)))
Output:
Maximum contiguous sum is -3Time and Space Complexity
As already discussed in the above code it runs in linear time and with constant space. Hence if you will put it in Big O Notation it will be as below.
Time Complexity:
O(n)
Space Complexity:
O(1)
Note: Above code can be implemented in various other ways for example instead of using the if condition to compare the values and assign instead of that you can simply use the max method present in almost all programming languages.
Let us see how to make the above code more optimized in terms of line.
#include<bits/stdc++.h>
using namespace std;
//Calculation of Maximum Sub using Kadane's Algorithm
//Here Maximum sum may be negative as well.
int getMaxSubArraySum(vector<int> &givenArray, int size){
int maxSumSubArray = INT_MIN;
int currentMaxValue = 0;
for (int i = 0; i < size; i++)
{
currentMaxValue = max(givenArray[i], givenArray[i] + currentMaxValue);
maxSumSubArray = max(maxSumSubArray, currentMaxValue);
}
return maxSumSubArray ;
}
/*Driver program to test Get the Maximum Sum of Contiguous Sub Array*/
int main()
{
vector<int> givenArray = {-1,1,2,2,-1,-3,-1,0,3};
int size = givenArray.size();
int maxSumSubArrayVal = getMaxSubArraySum(givenArray, size);
cout << "Maximum contiguous sum is " << maxSumSubArrayVal;
return 0;
}
# Find maximum contiguous subarray using Kadane's Algorithm
#Function Implementing the Above Psuedo Code to get
#Maximum Sum of Sub Array using Kadane's Algorithm
def getMaxSubArraySum(givenArray,size):
#Since in Python 3 we Donot have MAXINT
# Hence Negative Infinity can be represented as below
maxSumSubArray = float('-inf')
currentMaxValue = 0
for i in range(0, size):
currentMaxValue = max(givenArray[i], currentMaxValue + givenArray[i])
maxSumSubArray = max(maxSumSubArray, currentMaxValue)
return maxSumSubArray
# Driver function to check the above function
givenArray = [-1,-2,0,1,3,5,-1,2,4,1,0,1,-10]
print("Maximum contiguous sum is", getMaxSubArraySum(givenArray,len(givenArray)))
Output:
That is all for Kadane’s Algorithm Maximum Sum Subarray Problem. Let me know if you have any questions in the comment section. Also, let me know if you want the code in a different language as well.
And please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.
Further Read:
