## Sunday, August 22, 2010

### Finding Maximum Sum of Sub Sequence

Given an array of integers, find the maximum sum of Sub Sequence.

For example, if the array is, 4 5 6 -2 3 4 -10 1 2 3, then the maximum sum is 20, and the range is 0 to 5.

If the array is, 1 2 3 -10 4 5 6 -2 3 4, then the maximum sum is 20, and the range is 4 to 9.

```#include<stdio.h>
main()
{
int i, n;
int a;
int start=-1, end=-1, sum=0;
int maxstart=-1, maxend=-1, maxsum=0;
printf("Enter the count: ");
scanf("%d", &n);
printf("Enter the numbers\n");
for(i=0; i<n; i++) {
scanf("%d", &a[i]);
}
start = 0;
end = 0;
for(i=0; i<n; i++) {
sum += a[i];
end = i;
if(sum < 0) {
start = i+1;
sum = 0;
}
if(sum > maxsum) {
maxstart = start;
maxend = end;
maxsum = sum;
}
}
printf("sum = %d\nstart = %d\nend = %d\n", maxsum, maxstart, maxend);
}
```

1. I don't believe this question is asked correctly for the given answer.
You want the contiguous sub-sequence with the maximum sum. A subset is not ordered, and would thus a subset with the maximal sum would be the given by the sum of the positive values. It would be 28 in both cases.
I hope this wasn't actually the way the interview was done.

2. Thanks for pointing the mistake. I corrected it. I was expecting contiguous subset, and not the normal subset.

3. Will this work if all the elements are negative?

4. Call it a sub-sequence, not a subset.

5. Thanks Anonymous. I corrected it.

6. Nitin,
I guess, it works, even if all the elements are negative. It prints indexes as -1, and sum as 0.

7. same negative question again: what will be its output for: -2 -1 -3 -4 -5 -6 -7 -8 -9 -10