Answer to Question #205026 in C for Arunan Naicker

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 <stddef.h>
#include <float.h>
#include <assert.h>


typedef struct {
  size_t start;
  size_t finish;
  double sum;
} MaxSequence;

MaxSequence LagestSum(double* array, size_t size) {
  assert(array != NULL);

  double max = DBL_MIN, max_end = 0.0;
  size_t start = 0, end = 0, s = 0;
  for (size_t i = 0; i < size; i++) {
    max_end += array[i];
    if (max < max_end) {
      max = max_end;
      start = s;
      end = i;
    }
    if (max_end < 0) {
      max_end = 0;
      s = i + 1;
    }
  }
  MaxSequence result;
  result.start = start;
  result.finish = end;
  result.sum = max;
  return result;
}

int main() {
  double array[] = { -3, 4, 2, 1, -4, 6, -10, 0, -4, 3 };
  MaxSequence seq = LagestSum(array, sizeof(array) / sizeof(array[0]));
  printf("START: %d, FINISH: %d, MAX: %lf\n", seq.start, seq.finish, seq.sum);
  return 0;
}