如何提高该算法的时间复杂度来寻找最大股价？

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 对于某些测试用例的链接，但将在一段时间后过期。你知道吗

问题

你的算法已经变得非常善于预测市场，以至于你现在知道Woodon Orange牙签公司（WOT）未来几天的股价。你知道吗

每天，你可以买一股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

如果你能使用Numpy，那么类似下面的东西应该是相当快的（我相信这和@1490;㪞דברקן的答案是一样的想法）。你知道吗

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 2

显然，无论我们能以什么价格购买，我们都希望以最高的价格出售。幸运的是，我们得到了最高的价格。所以，通过反向迭代，我们知道在“回到过去”的旅行中，我们所看到的任何时刻的最高未来价格

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]