P144 不限次数进行股票买卖的最大利润

描述#

这个题目说的是，给你一个整数数组，其中第 i 个元素表示的是第 i 天的股票价格，在不限制买卖次数的情况下，你要计算出买卖股票可以获得的最大利润。注意，你不能同时参与到多个交易当中，也就是你要先卖掉手上的股票，才能买进新的一股。

比如说，给你的数组是：
2, 1, 2, 4, 2, 8, 4
你在价格为 1 时买入并在价格为 4 的時候卖出，获得利润 3；然后在价格为 2 时买入并在价格为 8 时卖出，获得利润 6。这个买卖组合可以获得最大利润 9。
再比如说给你的数组是：
8, 4, 2, 1
这时股票每天都在迭，不存在买入再卖出来获利的可能，因此没有交易，最大利润为 0。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int maxProfitLocalMaxMin(int[] prices) {
    if (prices == null || prices.length == 0) return 0;
    int profit = 0, buyPrice, sellPrice;
    int i = 0, n = prices.length;
    while (i < n-1) {
      while (i < n-1 && prices[i+1] <= prices[i]) ++i;
      buyPrice = prices[i];
      while (i < n-1 && prices[i+1] >= prices[i]) ++i;
      sellPrice = prices[i];
      profit += (sellPrice - buyPrice);
    }
    return profit;
  }

  // Time: O(n), Space: O(1)
  public int maxProfitGreedy(int[] prices) {
    if (prices == null || prices.length == 0) return 0;
    int profit = 0;
    for (int i = 1; i < prices.length; ++i)
      if (prices[i] > prices[i-1])
        profit += (prices[i] - prices[i-1]);
    return profit;
  }

}