algorithm - find longest subsequence with non-negative sum -

let's have array of n real numbers. want find longest contiguous subsequence in array it's sum greater or equal zero.

it has done in linear time.

we have no idea how start answering this.

thanks in advance.

for this, create subsequence (here designated ibeg, iend, , length len) , march along sequence, extending subsequence @ end or shrinking @ beginning maintain >0. since inner loop constrained length of current sequence 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 = 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 length of longest sequence, , best_ibeg , best_iend starts , ends, respectively.