Largest Sum Contigous SubArray in C

Largest Sum Contigous SubArray

 

Here, in this page we will discuss the C program to find the largest sum contigous Subarray. We use Kadane’s algorithm, which runs in O(n) time.
The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position.

Contigous SubArray in C

Algorithm :

 

  • Create two intermediate variables max_ending_here  and max_so_far.

  • Initialized these two intermediate variables using the 0.

  •  Traverse the array from 0 to N-1 and calculate the max_ending_here and max_so_far.

  • Now we will keep max_so_far which indicates the maximum sum found so far.
Contigous SubArray

Code in C based on above approach

#include <stdio.h>
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

int maxSubArraySum(int arr[], int n)
{
int i =0;
int max_so_far = 0;
int max_ending_here = 0;

for ( i = 0; i < n; i++)
{
max_ending_here = max_ending_here + arr[i];
if (max_ending_here < 0)
{
max_ending_here = 0;
}
if (max_so_far < max_ending_here)
{
max_so_far = max_ending_here;
}
}
return max_so_far;
}
int main()
{
int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int arr_size = ARRAY_SIZE(arr);
const int maxSum = maxSubArraySum(arr, arr_size);
printf("Largest Sum Contigous SubArray : %d ", maxSum);
return 0;
}
Output :


Largest Sum Contigous SubArray : 6