Maximum Sub-Array Sum : Kadane's Algorithm

Originally Posted on SeedBx

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|²)

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

• At index 1, we update the value of currSum=max(12, 12+23)=35 and maxSum=max(12, 35).

• At index 2, we update the value of currSum=max((-38), 35+(-38))=-3 whereas the value of maxSum remains unchanged.

• At index 3, we update the value of currSum=max(1, 1+(-3))=1 and the value of maxSum remains unchanged.

• At index 4, we update the value of currSum=max(2, 2+1)=3 and the value of maxSum remains unchanged.

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.

Thanks for reading.