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[100]; 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); }

I don't believe this question is asked correctly for the given answer.

ReplyDeleteYou 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.

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

ReplyDeleteWill this work if all the elements are negative?

ReplyDeleteCall it a sub-sequence, not a subset.

ReplyDeleteThanks Anonymous. I corrected it.

ReplyDeleteNitin,

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

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

ReplyDelete