Home » Algorithms

Find the maximum sub-array sum using KADANE'S ALGORITHM

C++ program to find the maximum sub-array 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 sub-array?

A sub-array is basically an array's contiguous part. For example, if we have an array of integers [1,2,3] so the sub-arrays 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 sub-arrays are 1,2,3,3,5,6. So here in this problem, we are required to find the maximum sub-array 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 brute-force algorithm can be → that we can simply compute the sum of all the sub-arrays 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 pre-computation 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 sub-array 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

1. Initialize two variables named CS (current sum) and MS (max sum) with 0
2. Loop for each element of the array and do these below tasks for each iteration,
   1. CS = CS + ar[i]
   2. If(CS<0) then CS=0
   3. (C) If(MS<CS) then MS=CS

Description: So basically if we have to find the maximum sub-array 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