algorithm - 计算任何 30 天期间的最大总和

Question

我的数据如下：

Date        Value
2011-01-01  1
2011-01-02  5
2011-01-03  30
   .....
2012-01-01  4

我想计算我的数据中哪个 30 天的时间段具有最大的值总和。

不确定我的问题是否有意义，因为我的数学头脑不好，很难解释。

谢谢史蒂夫

Answer 1

这应该为你做。它假定基于零 (0) 的阵列系统。

总和 <- 0
对于 i = 0 到 29
  总和 <- 总和 + 值（i）

最大值 <- 总和
开始 <- 0

对于 i = 30 到 value.lengh-1
  sum <- sum - value(i-30) + value(i)
  如果总和 > 最大值则
    最大值 <- 总和
    开始 <- i-29

这里max包含 30 个连续值的最大总和，并start包含 30 天最大运行的起点。

Answer 2

伪代码：

MaxStartDate = FirstDate
MaxTotal = -1   (something that is definitely below your possible total)

for n=0 to lastDate-30
{
    tempMax = 0

    for m=n to n+29
        tempMax = tempMax + date(m)

    if tempMax > MaxTotal
    {
        MaxTotal = tempMax
        MaxStartDate = date(n)
    }
}

当 for 循环结束时，MaxTotal 将是您最高的 30 天总数，MaxStartDate 将是 30 天集合中的第一天。

Answer 3

for first 30 days in your data, compute the sum of all values
let this be called as max_sum
let start_date be the first date in the input data

Loop 'i' from 1 to (total dates - 30)
    temp_sum = (temp_sum + value of date (30+i) - value of date (i))
    if max_sum < temp_sum
       max_sum = temp_sum
       start_date= ith date

的最终值max_sum是以任何 30 天start_date为起点的值的最大总和。