如何提高该算法求出最大股价的时间复杂度？

Question

我目前正在通过样本测试和其他10例中的2例，因此12例中有4例。然而，我并没有通过所有的数据。由于超时错误，我将被终止，这意味着我的解决方案不够快。

def stockmax(prices):
    total = 0 
    for index, price in enumerate(prices):
        if index < len(prices) - 1: 
            section = max(prices[index+1:])

            if prices[index] < section:
                total += section - prices[index]
    return total

我试着只在一个循环中完成所有的事情。但如何才能加快这类问题的速度。我还试图减少代码中的一些行，但这同样是低效的。

def stockmax(prices):
    total = 0 
    for index, price in enumerate(prices):
        if index < len(prices) - 1 and prices[index] < max(prices[index+1:]): 
              total += max(prices[index+1:]) - prices[index]
    return total

尽管它通过了相同数量的测试用例。我也尝试使用heapq，但是它通过了相同的测试用例，并且由于时间关系而失败。

def stockmax(prices):
    total = 0 
    for index, price in enumerate(prices):
        if index < len(prices) - 1:
            section = heapq.nlargest(1,prices[index+1:])[0]
            if prices[index] < section: 
                total += section - prices[index]
    return total

有关此问题的详细信息，请参见https://www.hackerrank.com/challenges/stockmax/topics/dynamic-programming-basics。

https://hr-testcases-us-east-1.s3.amazonaws.com/330/input09.txt?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1538902058&Signature=3%2FnfZzPO8XKRNyGG0Yu9qJIptgk%3D&response-content-type=text%2Fplain用于某些测试用例的链接，但将在一段时间后过期。

问题

你的算法在预测市场方面变得如此出色，以至于你现在知道了木橙牙签公司未来几天的股价。

每天，你都可以买一股WOT股票，出售你所拥有的任何数量的WOT股票，或者根本不做任何交易。通过最优的交易策略，你能获得的最大利润是多少？

例如，如果你知道接下来两天的价格是prices = [1,2]，你应该在第一天买一股，然后第二天卖掉它，以1的利润出售。如果它们是prices = [2,1]，那就没有利润，所以你在那些日子里不会买卖股票。

功能描述

在下面的编辑器中完成stockmax函数。它必须返回一个整数，该整数代表可实现的最大利润。

stockmax具有以下参数：

价格:代表预测日股价的一组整数。

输入格式

第一行包含测试用例t的数量。

接下来的每一对t行都包含：

• 第一行包含一个整数n，即WOT的预测价格数。
• 下一行包含n个空格分隔的整数prices [i]，每个整数都是日i的预测股价.

约束条件

1 <= t  <= 10
1 <= n <= 50000
1 <= prices [i] <= 100000

输出格式

输出线，每一行包含可为相应测试用例获得的最大利润。

样本输入

3
3
5 3 2
3
1 2 100
4
1 3 1 2

样本输出

0
197
3

解释

对于第一种情况，你不可能获得任何利润，因为股价永远不会上涨。在第二种情况下，你可以在前两天购买一股股票，在第三天卖出两只股票。对于第三种情况，你可以在第一天买一股，在第二天卖出一股，在第三天买一股，在第四天卖出一股。

Answer 1

显然，对于我们能买到的任何价格，我们都想以最高的价格出售。幸运的是，我们得到了最高的价格。所以，反反复复，我们知道我们在旅行中“回到过去”的任何时刻看到的最高的未来价格。

Python代码：

def stockmax(prices):
  n = len(prices)
  highest = prices[n - 1]
  m = [0] * n

  # Travel back in time,
  # deciding whether to buy or not
  for i in xrange(n - 2, -1, -1):

    # The most profit buying stock at this point
    # is what we may have made the next day
    # (which is stored in m[i + 1])
    # and what we could make if we bought today
    m[i] = m[i + 1] + max(
      # buy
      highest - prices[i],
      # don't buy
      0
    )

    # Update the highest "future price"
    highest = max(highest, prices[i])

  return m[0]

Answer 2

如果您可以使用Numpy，那么类似于下面的内容应该会很快(我相信这与@גלעדברקן的答案相同)。

import numpy as np

with open('.../input09.txt') as fd:
    numtests = int(fd.readline().strip())
    counter = 0
    numvals = 0
    vals = None
    steps = None
    for line in fd:
        if (counter % 2 == 0) :
            numvals = int(line.strip())
        else:
            vals = np.fromstring(line, dtype=int, sep=' ', count=numvals)
            assert len(vals) == numvals

            cum_max = np.maximum.accumulate(vals[::-1])
            np.roll(cum_max, -1)
            cum_max[len(cum_max) - 1] = 0
            delta = (cum_max - vals)
            print('#', counter + 1, 'sum:', np.sum(delta * (delta > 0)))

        counter += 1

它几乎立即在input09.txt的测试中运行。

Answer 3

这是我用红宝石写的解决方案。解得到了满分。

def solution(a)
  gain = 0
  i = a.count - 1
  min = false
  mi = false

  while i > 0
    s = a.delete_at(i)

    unless min
      mi = a.index(a.min)
      min = a[mi]
    end
    g = s - min
    gain = g if g > gain
    i -= 1
    min = false if i == mi
  end
  gain
end