2

问题：给定一个向量，我想知道一系列累积和的最小值，其中每个累积和是针对向量的递增起始索引和固定结束索引（1：5、2：5，... , 5:5)。具体来说，我想知道这是否可以使用for()循环来计算，以及是否有可能用于该算法/计算的术语。我在 R 工作。

上下文：感兴趣的向量包含压力变化的时间序列。我想知道在一系列起点但具有固定终点的压力的最大（或最小）净变化。

详细信息+示例：

#Example R code    
diffP <- c(0, -1,  0,  1,  0,  0,  1,  0,  0,  0,  0,  0, -1,  0,  0,  0,  0,  0,  0,  0, -1,  0,  0)
minNet1 <- min(cumsum(diffP))
minNet1 #over the whole vector, the "biggest net drop" (largest magnitude with negative sign) is -1.
#However, if I started a cumulative sum in the second half of diffP, I would get a net pressure change of -2.
hold <- list()
nDiff <- length(diffP)
for(j in 1:nDiff){
   hold[[j]] <- cumsum(diffP[j:nDiff])
}
answer <- min(unlist(hold)) #this gives the answer that I ultimately want

希望我上面的例子有助于阐明我的问题。answer包含正确的答案，但我宁愿for()在 R 中没有循环的情况下这样做。有没有更好的方法来做这个计算，或者我可以给它一个名字？

4

1 回答 1

3

这被称为http://en.wikipedia.org/wiki/Maximum_subarray_problem，是一个典型的面试问题！

大多数人——包括我——会使用 O(n^2) 算法来解决它，但实际上有一个更好的算法，复杂度为 O(n)。这是上面链接中 Kadane 算法的 R 实现：

max_subarray <- function(A) {
   max_ending_here <- 0
   max_so_far <- 0
   for (x in A) {
      max_ending_here <- max(0, max_ending_here + x)
      max_so_far <- max(max_so_far, max_ending_here)
   }
   max_so_far
}

由于在您的情况下，您正在寻找最小的子数组总和，因此您必须这样称呼它：

-max_subarray(-diffP)
[1] -2

（或者你也可以重写上面的函数并替换max为min到处。）

请注意，是的，实现仍然使用for循环，但算法的复杂度为 O(n)（意味着操作的数量与 的顺序相同length(diff)），它应该相当快。此外，它不会消耗任何内存，因为它只存储和更新几个变量。

于 2013-08-28T19:22:41.647 回答