描述

• 假定你知道某只股票每一天价格的变动。
  你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。
  请设计一个函数，计算你所能获得的最大收益。

方法一

思路

• 正反两次循环遍历

• 题目明确指出最多可以进行两次交易，且这两次交易在时间上是有先后次序的（最多可以同时持有一只股票）；

• 首先假设在进行两次交易时，所获收益最大，假设第一次交易为A，第二次交易为B；即交易A发生在交易B之前；

• 此时我们知道A与B之间在时间上必然是没有重叠部分的（当天卖出当天买入算作没有重叠），假设A发生在第1~i天，那么B必然发生在第i~n天（忽略当天买入天卖出的情况）；

• 所以便能够得出如下的公式：

  
  i的取值范围1~n；

• 依据上述公式，首先进行反向遍历找出从第i天到第n天最大利润，使用一维数组做记录（第二次交易）；

• 接着进行正向遍历，找出最大利润（正向和反向的遍历顺序不是固定的，可以切换）。

• 观察下图栗子，你会发现对于只进行一次交易，当天买入当天卖出以及不进行交易的情况均满足上述公式：
  
  
  
  

• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int res = 0;
        // 数组中只有一个元素或为空，返回0
        if (prices.length < 2){
            return res;
        }
        // 首先找出第二次交易能够获得的最大利润
        // secondProfits[i]表示从第i-1天开始到
        // 结尾的一次交易能够获得的最大利润
        int[] secondProfits = new int[prices.length];
        int len = prices.length-1;
        // 最大价格
        int max = prices[len];
        // 从后往前遍历，最后一天买入卖出的利润为0
        for(int i = len - 1;i >= 0;--i){
            // 更新股票最大值
            max = Math.max(max,prices[i]);
            // 计算从第i-1天到结尾的最大利润
            secondProfits[i] = Math.max(secondProfits[i+1],
                                        max - prices[i]);
        }
        // 从前往后遍历时的股票价格最小值
        int min = Integer.MAX_VALUE;
        for (int i = 0;i < len;++i){
            // 更新最低股票价格
            min = Math.min(min,prices[i]);
            // 找出两次交易最大利润的组合
            res = Math.max(res,prices[i] -
                           min + secondProfits[i+1]);
        }
        return res;
    }
  }

• 时间复杂度：，两次单层循环；

• 空间复杂度：，使用一维数组辅助运算。

方法二

思路

• 状态转换；

• 方法一的空间复杂度为，可以考虑将其降低为；

• 方法一采用一维数组来记录第二次交易的利润，那么本方法所考虑的就是不使用一维数组来记录第二次交易的利润，直接找出两次交易最大利润的组合；

• 考虑状态机，分别有四个状态：第一次买入，第一次卖出，第二次买入，第二次卖出，且由方法一的分析易得出以下的状态转换关系：
  
  定义这四种状态的利润分别为A,B,C,D（初始值为0）；那么由上述状态图得知：

  
  
  
  

• 那么这能满足题目要求吗？

• 很明显它是无法满足的，你很容易在方法一的图四中发现这个状态转换关系是无法正确的找出最大收益的；

• 你可以发现这个上述状态转移是随着i而变换的，它直接丢弃了之前计算的最大利润（D即为最大利润），所以当i增大，往前计算所能得到的最大利润同时，需要记录之前已经找到的最大利润的记录，所以需要在上述状态转换关系的基础上添加下述转换关系：

  
  
  
  
  状态图如下：
  

• 综上，状态转换关系如下：

  
  
  
  

• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // 数组中只有一个元素或为空，返回0
        if (prices.length < 2){
            return 0;
        }
        // 第一次买入
        int firstBuy = -prices[0];
        // 第一次卖出
        int firstSell = 0;
        // 第二次买入
        int secondBuy = -prices[0];
        // 第二次卖出
        int secondSell = 0;
        // 遍历prices数组，找出最大利润
        // 更新状态变量
        for(Integer price : prices){
            firstBuy = Math.max(firstBuy,-price);
            firstSell = Math.max(firstSell,firstBuy + price);
            secondBuy = Math.max(secondBuy,firstSell - price);
            secondSell = Math.max(secondSell,secondBuy + price);
        }
        return secondSell;
    }
  }

• 时间复杂度：，遍历数组；

• 空间复杂度：，常数级空间复杂度。