Answer to Question #204930 in C for Elaine

Question

Exercise 1: Largest contiguous partial sum

(a) Write a function that will find the largest contiguous partial sum, LagestSum, within an array of real numbers. That is,

we want to sum up any number of neighboring elements from the array, starting from anywhere, find the largest possible

sum.

-3 4 2 1 -4 6 -10 0 -4 3

then the function should report return 9, because 4+2+1+(-4)+6= 9 is the largest sum of contiguous elements from that array of numbers. The function must also provide the starting and the ending indices of the summed elements back to its caller(indices 1 and 5 for the example above).

(b) Write a driver program that tests the function LargesttSum written in (a).

Answer 1

#include<stdio.h>
#include<stdlib.h>


int max(int num1, int num2)
{
    return (num1 > num2 ) ? num1 : num2;
}
int maxSubArraySum(int a[], int size)
{
   int max_so_far = a[0];
   int curr_max = a[0];


   for (int i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}


int main()
{
   int a[] =  {-3, 4, 2, 1, -4, 6, -10, 0, -4, 3};
   int n = sizeof(a)/sizeof(a[0]);
   int max_sum = maxSubArraySum(a, n);
   printf("Maximum contiguous sum is %d",max_sum);
   return 0;
}