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