C Program to Find the Sum of Contiguous Subarray within a 1 – D Array of Numbers which has the Largest Sum


  1. /*
  2.  * C Program to Find the Sum of Contiguous Subarray within a 1 - D Array of Numbers which has the Largest Sum
  3.  */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. 
    
  7. int maxSubArraySum(int a[], int size, int *begin, int *end)
  8. {
  9.     int max_so_far = 0, max_end = 0;
  10.     int i, current_index = 0;
  11. 
    
  12.     for (i = 0; i < size; i++)
  13.     {
  14.         max_end = max_end + a[i];
  15.         if (max_end <= 0)
  16.         {
  17.             max_end = 0;
  18.             current_index = i + 1;
  19.         }
  20.         else if (max_so_far < max_end)
  21.         {
  22.             max_so_far = max_end;
  23.             *begin = current_index;
  24.             *end = i;
  25.         }
  26.    }
  27.    return max_so_far;
  28. }
  29. 
    
  30. int main()
  31. {
  32.     int arr[] = {10, -2, 15, 9, -8, 12, 20, -5};
  33.     int start = 0, end = 0;
  34.     int size = sizeof(arr) / sizeof(arr[0]);
  35. 
    
  36.     printf(" The max sum is %d", maxSubArraySum(arr, size, &start, &end));
  37.     printf(" The begin and End are %d & %d", start, end);
  38.     getchar();
  39.     return 0;
  40. }
output:
The max sum is 56 The begin and End are 0 & 6