Search

0.5.1.1.2 Source Code

Below is the source code to the divide and conquer maximum subsequence problem in C:

#include <stdio.h>

#define MAXSEQ 400

int numbers[MAXSEQ];
int endat;
int doit(int, int);

int main(void) {
  int i = 0;
  int num;
  int count;

  printf("enter the numbers, -99999 to end... \n");
  
  do {
    scanf("%d", &num);
    numbers[i] = num;
    i++;
  } while (num != -99999);
  count = i - 1;

  printf("max subseq value was %d end at %d\n", doit(0, count), endat);
}


int doit(int l, int r) {
  int mid;
  int ma, mb, mc;
  int i, sum, max;

  if (l == r) {
    return(numbers[l]);

  } else {
    mid = (l + r) / 2;

    if (mid == l) {
      ma = doit(l, l);
      mb = doit(r, r);
    } else {
      ma = doit(l, mid);
      mb = doit(mid, r);
    }

    /* now build mc */
    i = 1;
    sum = numbers[mid];
    max = numbers[mid];

    /* work our way right adding to the sum at each step */
    while ((mid + i) <= r) {
      sum += numbers[mid + i];
      if (sum > max) max = sum;
      i++;
    }
    mc = max - numbers[mid];

    i = 1;
    sum = numbers[mid];
    max = numbers[mid];

    /* now work left */
    while ((mid - i) >= l) {
      sum += numbers[mid - i];
      if (sum > max) max = sum;
      i++;
    }
    mc += max;

    if (mc > mb)
      if (mc > ma)
	return(mc);
      else
	return(ma);
    else
      if (mb > ma)
	return(mb);
      else
	return(ma);
  }
}