Monday, 13 March 2017

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,, 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.


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: ");
    printf("\nEnter the elements of array: \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;
    return max_sum_so_far;


See also: Implementation of Kadane Algorithm in Python