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

7 comments:

  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.

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

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

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

    ReplyDelete
  5. Thanks Anonymous. I corrected it.

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

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

    ReplyDelete