CODEWITHSUNDEEP
algorithmsubsequence
user76508
user76508

Reputation: 267

find longest subsequence with non-negative sum

Let's say we have an array of n real numbers. We want to find the longest contiguous subsequence in the array that it's sum is greater or equal zero.

It has to be done in linear time.

We actually have no idea how to start answering this.

Thanks in advance.

Upvotes: 0

Views: 1014

Answers (1)

Matt Phillips
Matt Phillips

Reputation: 9691

For this, create a subsequence (here designated with ibeg, iend, and length len) and basically march along the sequence, extending the subsequence at the end or shrinking it at the beginning to maintain >0. Since the inner loop is constrained by the length of the current sequence it is still O(N).

var ibeg = 0;
var iend = 0;
var len = 0;
var best_len = -1, best_ibeg = 0, best_iend = 0;

var acc = 0;
var i = 0;
var N = length(sequence);
while i<N
   acc += sequence(i);
   len++;
   iend++;
   if acc>0
      if len>best_len
          best_len = len;
          best_ibeg = ibeg;
          best_iend = iend;
      end
   else
      while ibeg<=iend
          acc -= sequence(ibeg);
          ibeg++;
          if acc>0, break; end
      end
   end
end

Then best_len will be the length of the longest sequence, and best_ibeg and best_iend will be where it starts and ends, respectively.

Upvotes: 1

Related Questions