Largest Contiguous Sum of Sub Array

Today's Post is about finding the Largest Contiguous Sum of A sub Array.

The Approach which i will use is called KADANE'S ALGORITHM

The very simple yet intuitive and efficient Kadane's algorithm works as follows:

Keep adding all the elements of array and keep the track of two things first whether the sum we are adding is positive or not,if its negative then again initialize it to zero. Second whether the sum calculated so is the biggest/largest of all or not.

Here's the code :

#include<stdio.h>

void findsum(int arr[],int n)
{
    int i=0,max_so_far=0,max_ending_here=0;

    for(i-0;i<n;i++)
    {
     max_ending_here=max_ending_here+arr[i];
     if(max_ending_here<0)
        max_ending_here=0;
     if(max_ending_here>max_so_far)
     max_so_far=max_ending_here;

    }
    printf("%d",max_so_far);
}

int main()
{
    int arr[]= {-2, -3, 4, -1, -2, 1, 5, -3};
    int n=sizeof(arr)/sizeof(arr[0]);
    findsum(arr,n);
    return 0;
}

Viva La Raza

Sid