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

8 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
  8. Knowing the secret arithmetic that a 토토사이트 slot machine uses to create pseudorandom outcomes isn’t enough to assist hackers, although. That’s outcome of|as a end result of} the inputs for a PRNG range relying on the temporal state of each machine. The seeds are different at different occasions, for example, as is the information culled from the interior clocks. So even if they understand how a machine’s PRNG functions, hackers would also have to investigate the machine’s gameplay to discern its sample.

    ReplyDelete