Home »
Algorithms
Find the maximum subarray sum using KADANE'S ALGORITHM
C++ program to find the maximum subarray sum using "KADANE'S ALGORITHM" which is the most optimized approach to perform the required task.
Submitted by Ankit Sood, on November 10, 2018
What is a subarray?
A subarray is basically an array's contiguous part. For example, if we have an array of integers [1,2,3] so the subarrays that we can form from the given array are [1], [2] , [3] , [1,2] , [2,3] , [1,2,3].
So in the above example the sum of all the respective subarrays are 1,2,3,3,5,6. So here in this problem, we are required to find the maximum subarray sum that could be obtained from a sequence of integers, which is 6 in the above case.
So many algorithms could be opted to solve the above problem, for example, a simple bruteforce algorithm can be → that we can simply compute the sum of all the subarrays then loop through all those sums to compute maximum of those, but this algorithm will take O(N*N*N) time or in the best case O(N*N) if we try to do some precomputation by making a cumulative some array also called a prefix sum array.
So now why should we prefer KADANES's ALGORITHM?
It is because this algorithm can solve our problem in O(N) time that is we can obtain the maximum subarray sum in linear time complexity which is the most optimal solution for our task.
So let us now quickly try to understand the Kadane's Algorithm in two simple steps.
KADANE's algorithm
 Initialize two variables named CS (current sum) and MS (max sum) with 0

Loop for each element of the array and do these below tasks for each iteration,
 CS = CS + ar[i]
 If(CS<0) then CS=0
 (C) If(MS<CS) then MS=CS
Description: So basically if we have to find the maximum subarray sum of a given array then the most optimal solution is KADANE'S ALGORITHM, which can easily perform the desired task in linear time complexity that is it will take O(N) time.
SO now let us quickly jump to the coding part!
Code:
#include <iostream>
using namespace std;
int main()
{
cout<<"Enter the size of an array: ";
int n;
cin>>n;
int ar[100],cs,ms;
ms=0;cs=0;
cout<<"Enter the array elements:"<<endl;
for(int i=0;i<n;i++)
cin>>ar[i];
for(int i=0;i<n;i++)
{
cs+=ar[i];
if(cs<0)
{
cs=0;
}
ms=max(cs,ms);
}
cout<<"The maximum subarray sum is: "<<endl;
cout<<ms;
return 0;
}
Output
Enter the size of an array: 6
Enter the array elements:
1 2 3 4 6 1
The maximum subarray sum is:
8
TOP Interview Coding Problems/Challenges