KADANE'S ALGORITHM:
Kadane's algorithm is an efficient solution for Maximum subarray problem with runtime complexity of O(n). This algorithm is an example of Dynamic Programming(the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem, the maximum subarray ending at the previous position)
Maximum subarray problem:
Given an array, our task is to find a contiguous subarray whose sum is maximum. For eg. consider an array {-1,4,-2,5,-5,2,-20,6}. The solution is a subarray {4,-2,5} whose sum is 7 which is the maximum sum possible from the given array.
Algorithm:
Kadane's Algorithm(array[1..n])
begin
(maxSum, maxStartIndex, maxEndIndex) := (-INFINITY, 0, 0)
currentMaxSum := 0
currentStartIndex := 1
for currentEndIndex := 1 to n do
currentMaxSum := currentMaxSum + array[currentEndIndex]
if currentMaxSum > maxSum then
(maxSum, maxStartIndex, maxEndIndex) := (currentMaxSum, currentStartIndex, currentEndIndex)
endif
if currentMaxSum < 0 then
currentMaxSum := 0
currentStartIndex := currentEndIndex + 1
endif
endfor
return (maxSum, maxStartIndex, maxEndIndex)
end
Program:
#include<stdio.h>
int main()
{
int maxSum=log(0), maxStartIndex=0, maxEndIndex=0;
//I'VE USED log(0) TO REPRESENT MINUS INFINITY.
//THIS IS THE WAY OF REPRESENTING MINUS INFINITY
//IN C :-)
int array[]={-1,4,-2,5,-5,2,-20,6};
int currentMaxSum=0,currentStartIndex= 0, currentEndIndex=0;
for(currentEndIndex=0;currentEndIndex<8;currentEndIndex++)
{
currentMaxSum = currentMaxSum + array[currentEndIndex];
if(currentMaxSum > maxSum)
{
maxSum=currentMaxSum;
maxStartIndex=currentStartIndex;
maxEndIndex=currentEndIndex;
}
if(currentMaxSum < 0)
{
currentMaxSum= 0;
currentStartIndex = currentEndIndex + 1;
}
}
printf("Max sum=%d\nStart Index=%d\nEnd Index=%d", maxSum,maxStartIndex,maxEndIndex);
getch();
return 0;
}
Output:
Max sum=7
Start Index=1
End Index=3
