Array is almost, in some way, in every application of programming and computer science in general. With array being so important in practical application any procedure on array becomes significant.

In this post we will look at the problem of finding maximum sub-array sum which can be done efficiently by using Kadane's Algorithm.

Problem Statement

Given an array of elements A, find the maximum sub-array sum.


Note : Sub-array is a collection or block of contiguous items in an array.

Example : For array A[]={1, 2, 3, 4}, {1, 2} is a sub-array whereas {1, 3} is not.


Naive Approach

Loosely speaking, we can traverse each and every subset that can be generated and calculate the sum for each and every possible subset.

Pseudo Code :

maxsum=0

for i=0 upto A.length
    sum=0
    for j=i+1 upto A.length
        sum=sum+A[j]
        if(sum>maxsum)
            maxsum=sum

Time Complexity : O(|A|2)

Space Complexity : O(|A|)


Kadane's Algorithm

The approach of Kadane's Algorithm is simple. We keep two flags, namely maxSum and currSum which store the global maximum and the local maximum respectively.

At each iteration we update the currSum as the maximum of currSum+currElement and  currElement.

  • If currSum + currElement is bigger then, we are adding to a sub-array started at a position before the currElement's position.
  • If currElement is bigger then, we are considering the sub-array that is starting at the currElement's position.

At each iteration, we also update the maxSum by checking if the local maximum is the global maximum i.e. we update maxSum to be the maximum of maxSum and currSum.

Example : Let us consider an array A[]={12, 23, -38, 1, 2}.

  • We initialise maxSum, currSum with the value at A[0].
Array at index 0
  • At index 1, we update the value of currSum=max(12, 12+23)=35 and maxSum=max(12, 35).
Array at index 1
  • At index 2, we update the value of currSum=max((-38), 35+(-38))=-3 whereas the value of maxSum remains unchanged.
Array at index 2
  • At index 3, we update the value of currSum=max(1, 1+(-3))=1 and the value of maxSum remains unchanged.
Array at index 3
  • At index 4, we update the value of currSum=max(2, 2+1)=3 and the value of maxSum remains unchanged.
Array at index 4

Hence, the maximum sub-array sum for this array A is maxSum=35.


Pseudo Code :

maxSum=currSum=A[0]

for i=1 upto A.length
    currSum=max(A[i], currSum+A[i])
    maxSum=max(maxSum, currSum)

Time Complexity : O(|A|)

Space Complexity : O(|A|)


Kadane's Algorithm is one simple algorithm that in a very few lines of code finds the maximum sub-array sum of an array. This algorithm can be applied for business analysis to study sales, profits and losses so as to make judicial business decisions.