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 - 最后3个元素.但是使用我的代码,输出是2,1 - 前2个元素.

请帮助,谢谢!

Answer 1

您希望最大总和连续序列,但是反转.这个页面有我见过的最好的解释.

基本算法如下所示:

>>> 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

您必须添加代码以跟踪开始和结束的索引.