121. 买卖股票的最佳时机

给定一个数组，它的第i个元素是一支给定股票第i天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

  1. 输入: [7,1,5,3,6,4]
  2. 输出: 5
  3. 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
  4.      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:

  1. 输入: [7,6,4,3,1]
  2. 输出: 0
  3. 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题目要求得到能获取到的最大利润，且只允许进行一次交易，那么需要在最低价时买入，之后在最高价时卖出。相当于寻找数组中的两个索引位置i和j使得prices[j] - prices[i]的值最大，而且满足i < j。所以，使用minPrice记录当前遍历数组得到的最小值，maxProfit记录当前位置之前能够获取的最大利润。不断往后遍历数组，按照前面的原理更新minPrice和maxProfit：

  • 如果当前位置prices[i] < minPrice，计算可能的最大利润max(maxProfit, prices[i] - minPrice)；
  • 否则更新minPrice，继续往后判断

最后返回maxProfit。

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices.length == 0){
  4.             return 0;
  5.         }
  7.         int minprice = prices[0];
  8.         int maxprofit = 0;
  9.         for(int i = 1; i < prices.length; i++){
  10.             if(prices[i] >= minprice ){
  11.                 maxprofit = Math.max(maxprofit , prices[i] - minprice );
  12.             } else {
  13.                 minprice = prices[i];
  14.             }
  15.         }
  17.         return maxprofit ;
  18.     }
  19. }

122. 买卖股票的最佳时机 II

给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

  1. 输入: [7,1,5,3,6,4]
  2. 输出: 7
  3. 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  4.      随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

  1. 输入: [1,2,3,4,5]
  2. 输出: 4
  3. 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  4.      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
  5.      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

  1. 输入: [7,6,4,3,1]
  2. 输出: 0
  3. 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • $1 <= prices.length <= 3 * 10 ^ 4$
  • $0 <= prices[i] <= 10 ^ 4$

这道题同样是要求得出能获取到的最大利润，但是允许多次交易，只要交易是合法的就行（卖出在买入之后）。由于涉及到可能多次的买入卖出，所以需要明白股票的买卖策略：

  • 单独交易日：今天买$p_1$，明天卖$p_2$，所获取利润$p_2 - p_1$
  • 连续上涨日：第一天买入，最后一天卖出。假设交易日价格为$p1、p_2…p_n$，所获取利润等于$p_n - p_1 = (p_2 - p_1)+(p_3-p_2) + …+(p_n - p{n-1})$，相当于每天都交易
  • 连续下跌日：一卖必亏，所以不交易

因此，对于某一天来说决定是否交易，只需要看它相对于前一天是否是上涨的：

  • 如果上涨，交易，累计利润
  • 否则，不交易
  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.            if(prices == null){
  4.             return 0;
  5.         }
  7.         int maxprofit = 0;
  8.         for(int i = 1; i < prices.length; i++){
  9.             if(prices[i] > prices[i - 1]){
  10.                 maxprofit += prices[i] - prices[i - 1];
  11.             }
  12.         }
  14.         return maxprofit;
  15.     }
  16. }

123. 买卖股票的最佳时机 III

给定一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

  1. 输入: [3,3,5,0,0,3,1,4]
  2. 输出: 6
  3. 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
  4.      随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

  1. 输入: [1,2,3,4,5]
  2. 输出: 4
  3. 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
  4.      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
  5.      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

  1. 输入: [7,6,4,3,1] 
  2. 输出: 0 
  3. 解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

题目依然是要求获取到最大利润，不过限制了只能交易两笔，因此，需要我们在判断的过程中主要交易的次数。