Kadane’s Algorithm [ Macrosoft – Amazon – FlipKart ]

Problem: Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum.

Link

#include <stdio.h>

int main() {
	//code
	int t,n,i,a;
	int mx_end_here,mx_so_far;
	scanf("%d",&t);
	while(t--)
	{
	    scanf("%d",&n);
	    mx_end_here=0,mx_so_far=-1000;
	    for(i=0;i<n;i++)
	    {
	        scanf("%d",&a);
	        if(a<0)
	        {
	            if(mx_so_far<a)
	            mx_so_far=a;
	            mx_end_here=mx_end_here+a;
	            if(mx_end_here<0)
	            mx_end_here=0;
	        }
	        else if(a>=0)
	        {
	            mx_end_here=mx_end_here+a;
	            if(mx_end_here>mx_so_far)
	            mx_so_far=mx_end_here;
	        }
	    }
	    printf("%d\n",mx_so_far);
	}
	return 0;
}