# C Program to Find the Contiguous Sub-Array with Maximum Sum

This question has been asked in the interviews of the following companies:

Flipkart, Microsoft, FactSet, DE Shaw, Amazon, Morgan Stanley, MetLife, Housing.com, Visa, Teradata, Snapdeal, Samsung, Payu, Walmart, [24]7 Innovation Lab

In the question an array is given to you which is containing both positive and negative integers. You have to find the contiguous Sub-Array with Maximum Sum.

Approach:

In this question we will use Kadane's Algorithm which is given below.

1. Let n be the size of array
2. set: max_sum_so_far=arr[0]
3. set: max_here=0
4. do For i=0 to n-1:
5.       set: max_here=max_here+arr[i]
6.       If  max_sum_so_far<max_here:
7.               set: max_sum_so_far=max_here
8.       If  max_here<0:
9.               set: max_here=0
10. End ForLoop
11. return max_sum_so_far

Explanation of Algorithm:

Let arr[]= { 4, 5, -1, -3,  6, -7 }

Set: max_sum_so_far = arr[0]   // max_sum_so_far will keep the maximum sum we have ever                                                             seen in the array.
Set: max_here = 0                         // max_here will keep the sum till ith element of the array.

Pass 1, i=0:      arr[0]= 4,   max_here=4, max_sum_so_far=4
Pass 2, i=1:      arr[1]= 5,   max_here=9, max_sum_so_far=9
Pass 3, i=2:      arr[2]= -1,  max_here=8, max_sum_so_far=9
Pass 4, i=3:      arr[3]= -3,  max_here=5, max_sum_so_far=9
Pass 5, i=4:      arr[4]=  6,  max_here=11, max_sum_so_far=11
Pass 6, i=5:      arr[5]= -7,  max_here=4,  max_sum_so_far=11

Therefore, contiguous sub-array with maximum sum is { 4, 5, -1, -3, 6} with sum=11

Program: C Program to Find the Contiguous Sub-Array with Maximum sum is here.

```#include <stdio.h>
int main()
{
int n,arr[100],i,result;
printf("\nEnter the number of elements: ");
scanf("%d",&n);
printf("\nEnter the elements of array: \n");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("\nCotiguous sub-array maximum sum is: %d",result);
return 0;
}
{
int i,max_sum_so_far,max_here=0;
max_sum_so_far=arr[0];
for(i=0;i<n;i++)
{
max_here=max_here+arr[i];
if(max_sum_so_far<max_here)
{
max_sum_so_far=max_here;
}
if(max_here<0)
{
max_here=0;
}
}
return max_sum_so_far;
}```

Output: