Python：编写程序查找最大价格跌幅的时间段

Question

我需要解决这个问题，但我卡住了。

题目是写一个程序，找出给定价格列表中最大价格下降的时间段。例如，如果价格列表是 [300,301,303,299,300,298,301,305]，那么最大的价格下降发生在时间点2（价格303）到时间点5（价格298）之间。

下面是我的解决方案，但有个缺陷。

def maxdrop(p):
  high = low = drop = newhigh = 0
  for i in range(len(p)):
    if p[i] >= p[high]:
      newhigh = i # invariant: p[high] <= p[newhigh]
    else: # so: p[i] < p[high] <= p[newhigh]
      newdrop = p[newhigh] - p[i]
      if newdrop >= drop:
        high, low, drop = newhigh, i, newdrop
  return ((high, p[high]), (low, p[low]), drop)
def test():
  p = [20,22,19,20,24,18,21,24,27]
  print p, maxdrop(p)
  p = list(reversed(p))
  print p, maxdrop(p)
  if __name__ == "__main__":
  test()

如果你用下面这个列表试试：[2,1,2,3,4,3,2]

最大的下降应该发生在4,3,2这三个元素上。但我的代码输出的是2,1，也就是前两个元素。

请帮帮我，谢谢！

Answer 1

最好把所有的值都打印出来，看看结果是什么。

你代码的问题在于，当你写 p[i] > p[high] 的时候，你更新了 newhigh 的值，但 high 的值并没有改变。

你可以直接写成 p[i] > p[newhigh]，然后看看这样是否能得到正确的结果。我没有检查过这样是否会输出正确的结果，你可以自己试试看。

不过，你也可以随时使用上面提到的简化版本。

Answer 2

你想要找到一个连续的数列，它的和是最大的，但这个数列是反向的。这个页面上有我见过的最好的解释。

基本的算法大概是这样的：

>>> def min_sum_subsequence(seq):
...     minsofar = 0
...     minendinghere = 0
...     for s in seq:
...         # invariant: maxendinghere and maxsofar are accurate
...         # are accurate up to s
...         minendinghere = min(minendinghere + s, 0)
...         minsofar = min(minsofar, minendinghere)
...     return minsofar
... 
>>> series = [300,301,303,299,300,298,301,305]
>>> returns = [series[i] - series[i-1] for i in range(1, len(series))]
>>> min_sum_subsequence(returns)
-5

你需要添加一些代码来记录开始和结束的索引。

Answer 3

这是我尝试的结果。它在你给的所有例子上都能正确运行。

我基本上是遍历这个数组，当发现两个点之间有下降时，把第一个点叫做A，然后往前看，直到找到一个比A大的值。在这个区域内，我会记录下最小值。如果A和这个最小值之间的差距比我之前找到的更大，我就会把这个差距记下来。接着，我会从下一个比A大的点开始，继续寻找新的下降。

下面是代码。虽然它不是特别符合Python的风格，但效果还不错（如果需要更快，我会考虑用Cython）。另外，它还会返回下降的幅度。

def maxdrop(p):
    bestdrop = 0
    wheredrop = -1,-1
    i = 0
    while i < len(p) - 1:
        if p[i+1] < p[i]:
            bestlocal = p[i+1]
            wherelocal = i+1
            j = i + 1
            while j < len(p) - 1 and p[j + 1] < p[i]:
                j += 1
                if p[j] < bestlocal:
                    bestlocal = p[j]
                    wherelocal = j
            if p[i] - bestlocal > bestdrop:
                bestdrop = p[i] - bestlocal
                wheredrop = i, wherelocal
            i = j+1
        else:
            i += 1
    return bestdrop,wheredrop

你代码的一个大问题是，你只在找到新的高点后，才去看下一个值的最大下降。