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 kadane(int arr[],int n);
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]);
    }
    result=kadane(arr,n);
    printf("\nCotiguous sub-array maximum sum is: %d",result);
    return 0;
}
int kadane(int arr[],int n)
{
    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: 
 

See also: Implementation of Kadane Algorithm in Python