为什么这个最大的后续和代码有效？

Question

Rosetta Code 具有以下任务，描述为 here：

"Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements, that is, the elements of no other single subsequence add up to a value larger than this one. An empty subsequence is considered to have the sum of 0; thus if all elements are negative, the result must be the empty sequence."

这不是一个非常复杂的问题，可以在十行或更少的时间内轻松解决。但是，their R solution 让我感到困惑。我在下面复制了它：

max.subseq <- function(x) {
  cumulative <- cumsum(x)
  min.cumulative.so.far <- Reduce(min, cumulative, accumulate=TRUE)
  end <- which.max(cumulative-min.cumulative.so.far)
  begin <- which.min(c(0, cumulative[1:end]))
  if (end >= begin) x[begin:end] else x[c()]
}

特别是，我不明白为什么需要 min.cumulative.so.far 变量，最后一行检查某个最大值的索引是否大于最小值的索引的想法对我来说确实很奇怪.

那么为什么这段代码有效？我了解每个单独的函数及其输出，但我不知道为什么像这样将它们放在一起会起作用，或者为什么会选择更简单的 "generate a list of valid subsequences, and pick the one with the greatest sum" 方法。

Answer 1

让我们从 cumulative 的结果开始分解它。

min.cumulative.so.far将为您提供所有索引中当前索引前的最小值cumulative。
在下一步中，我们为序列的每个元素计算最佳子序列的 cumulative，从 min.cumulative.so.far 到每个索引处的值。 end 将是最佳子序列的结尾，可以是 1。
这就是有趣的地方：如果所有值都是负数，end 将为 1 而 cumulative[1:end] 的所有值将为负数，因此 which.min() 的结果将为2 因为该值小于 0（索引 1 处的值）。现在这将导致 begin 大于 end 并且该函数将 return 一个空向量。否则 begin 将被设置为索引 end 之前的最低值之后的第一个索引，正如我们已经确定的那样，它是基于 cumulative 处的最大子序列的最后一个元素指数 begin。这就是将 0 添加到矢量的原因。如果相关 min.so.far 为负数，则从向量中的下一个值开始。如果所有 cumulative 值都是正数，只需从头开始（添加的 0 将是最低值）。这一步中唯一发生的事情实际上是找到最小 cumulative 到索引 end 的索引。
return 就显得微不足道了。如上所述，如果所有值都是负数，则为空，否则从头到尾的总和最大的子序列 x。

极端情况：所有值为负

> x <-  -(1:10)
> cumulative <- cumsum(x)
> cumulative
 [1]  -1  -3  -6 -10 -15 -21 -28 -36 -45 -55
> min.cumulative.so.far <- Reduce(min, cumulative, accumulate=TRUE)
> min.cumulative.so.far
 [1]  -1  -3  -6 -10 -15 -21 -28 -36 -45 -55
> end <- which.max(cumulative-min.cumulative.so.far)
> end
[1] 1
> begin <- which.min(c(0, cumulative[1:end]))
# c(0, cumulative[1:end]) is c(0, -1) in this case as 1:end = 1:1
> begin
[1] 2
> if (end >= begin) x[begin:end] else x[c()]
integer(0)

标准案例

> x <- c(1, 5, -9, 3, 7, 1, 2, 4, 5, -6)
> cumulative <- cumsum(x)
> cumulative
 [1]  1  6 -3  0  7  8 10 14 19 13
> min.cumulative.so.far <- Reduce(min, cumulative, accumulate=TRUE)
> min.cumulative.so.far
 [1]  1  1 -3 -3 -3 -3 -3 -3 -3 -3
> end <- which.max(cumulative-min.cumulative.so.far)
> end
[1] 9
> begin <- which.min(c(0, cumulative[1:end]))
> begin
[1] 4
> if (end >= begin) x[begin:end] else x[c()]
[1] 3 7 1 2 4 5

为什么这个最大的后续和代码有效？

Why does this greatest subsequential sum code work?

r

sum

subsequence