algorithm - 找到具有非负和的最长子序列

Question

假设我们有一个包含 n 个实数的数组。我们想在数组中找到和大于或等于零的最长连续子序列。

它必须在线性时间内完成。

我们实际上不知道如何开始回答这个问题。

提前致谢。

Answer 1

为此，创建一个子序列(此处指定为 ibeg、iend 和长度 len)并基本上沿着序列行进，扩展最后的子序列或在开头缩小它以保持> 0。由于内层循环受到当前序列长度的限制，它仍然是 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

然后 best_len 将是最长序列的长度，best_ibeg 和 best_iend 将分别是它的开始和结束位置。