Size of sub-array with max sum in C

Size of sub-array with max sum

 

Here, in this page we will discuss the program to find size of sub-array with max sum in C. 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. If current sum becomes 0 then at that point we also update the starting index.

size of subarray with max sum

Algorithm :

 

  • Create two intermediate variables max_ending_here  and max_so_far .

  • And also two variables start and end for tracking start and the end index of the subarray with maximum sum.

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

  • During the scanning of  the elements from starting, and when the max_ending_here becomes 0 at that point we also update start and end variables.

 

Size of sub-array with max sum in C

Code for finding size of sub-array with max sum in C

#include<stdio.h>

int maxSubArraySum(int a[], int size)
{
int max_so_far = 0, max_ending_here = 0,
start =0, end = 0, s=0;

for (int i=0; i< size; i++ )
{
max_ending_here += a[i];

if (max_so_far < max_ending_here)
{
max_so_far = max_ending_here;
start = s;
end = i;
}

if (max_ending_here < 0)
{
max_ending_here = 0;
s = i + 1;
}
}

return (end - start + 1);
}

int main()
{
int a[] = {-7, 3, 4, -1, -12, 1, -9, -3};
int n = sizeof(a)/sizeof(a[0]);
printf("Size of subarray with maximum sum is : %d",maxSubArraySum(a, n));
return 0;
}
Output :

Size of subarray with maximum sum is : 2