java - 卖出股票的最大利润

Question

您的算法已经非常擅长预测市场，以至于您现在知道 Wood Orange Toothpicks Inc. (WOT) future 几天的股价将是多少。

每天，您可以购买一股 WOT，出售您拥有的任意数量的 WOT，或者根本不进行任何交易。通过最佳交易策略，您可以获得的最大利润是多少？

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

样本输入

3

3

5 3 2

3

1 2 100

4

1 3 1 2

样本输出

0

197

3

我的代码是:

static int stockmax(int[] prices) {
  int temp[][]=new int[prices.length][prices.length];
    int max;
    int sum=0;
    for(int i=0;i<prices.length;i++)
    {
        max=0;
        for(int j=0;j<prices.length;j++)
        {
            if(j<=i)
            {
                temp[i][j]=0;
            }
            else{
                temp[i][j]=prices[j]-prices[i];
            }
            if(temp[i][j]>max)
                max=temp[i][j];
        }
        sum+=max;
    }
    return sum;
}

我得到了这个问题的错误答案。谁能说为什么这段代码是错误的？

Answer 1

显然，对于我们可以购买的任何价格，我们都希望以最高价格出售。幸运的是，我们得到了最高的价格。因此，向后迭代，我们知道在我们“回到过去”旅行中访问的任何时间点看到的最高 future 价格。

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]