Search
Next: 0.5.1.2 Linear Solution Up: 0.5.1.1 Divide and Conquer Previous: 0.5.1.1.1 Analysis

#### 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);
}
}
```

Scott Gasch
1999-07-09