Find the maximum sum of contiguous subarray

Find the maximum sum of contiguous subarray (Kadane's algorithm)

Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (temp_sum). And keep track of maximum sum contiguous segment among all positive segments (max_sum). Each time we get a positive sum compare it with max_sum and update max_sum if it is greater than max_sum.

It solves the problem in O(n).

Note: This Algorithm doesn't work for all negative numbers and returns 0 for the same. For handling this we can add an extra line of code before actual implementation which returns the maximum number if all the number of the given array are negative.

Code:

#include<stdio.h>

int main(){
int temp_sum,i,max_sum;
int a[]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
//int a[]={1,-2,-3,4,5,6,7};
int n = sizeof(a)/sizeof(a[0]);
        temp_sum=0;
        max_sum=0;
        
        for(i=0;i<n;i++){
            temp_sum+=a[i];             

            if(temp_sum+a[i]<0)      
                 temp_sum=0;
            
            if(temp_sum>max_sum)
                 max_sum=temp_sum;
            
        }
        printf("Maximum contiguous sum: %d ",max_sum);

return 0;
}