题解 | #股票交易的最大收益（二）#

题意整理

• 已知股票每一天的价格波动
• 最多持有一只股，也就是买入时，必须卖出之前持有的股
• 最多交易两次，求最大收益

方法一（动态规划）

1.解题思路

本题的难点在于交易次数进行了限定，可以多开一维空间来存储交易次数。所以可以用三维dp来求解。

• 状态定义：第一维表示交易天数，第二维表示交易次数，第三维表示是否持有股票状态（分未持有股票和持有股票两种）。
• 状态转移：当某一天第k次交易，并处于未持有股票状态时，其最大值，要么是之前某一天第k次交易未持有股票状态的最大值，要么是之前某一天持有股票状态卖出当天的股票，即 ；当某一天第k次交易，并处于持有股票状态时，其最大值，要么是之前某一天第k次交易持有股票状态的最大值，要么是之前某一天第k-1次交易未持有股票状态买入当天的股票（不能同时持有两只股票），即 。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int n=prices.length;
        //最大交易次数
        int maxK=2;

        //初始化dp数组
        int[][][] dp=new int[n][maxK+1][2];
        for(int i=0;i<n;i++){
            for(int k=maxK;k>=1;k--){
                if(i==0){
                    //给每个状态赋初值
                    dp[i][k][0]=0;
                    dp[i][k][1]=-prices[0];
                }
                else{
                    //状态转移
                    dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
                    dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);      
                }

            }

        }
        return dp[n-1][2][0];
    }
}

3.复杂度分析

• 时间复杂度：最大交易次数maxK等于2，需要遍历两次数组，所以时间复杂度为 。
• 空间复杂度：需要额外 的空间,maxK为2，所以空间复杂度为。

方法二（动态规划+状态压缩）

1.解题思路

由于每天的状态只与前一天的有关，所以可以省去交易天数这一个维度。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int n=prices.length;
        //最大交易次数
        int maxK=2;

        //初始化dp数组
        int[][] dp=new int[maxK+1][2];
        for(int i=0;i<n;i++){
            for(int k=maxK;k>=1;k--){
                if(i==0){
                    //每种状态赋初值
                    dp[k][0]=0;
                    dp[k][1]=-prices[0];
                }
                else{
                    //状态转移
                    dp[k][0]=Math.max(dp[k][0],dp[k][1]+prices[i]);
                    dp[k][1]=Math.max(dp[k][1],dp[k-1][0]-prices[i]);      
                }

            }

        }
        return dp[2][0];
    }
}

3.复杂度分析

• 时间复杂度：只需要遍历两次数组，所以时间复杂度为。
• 空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为。

方法三（动态规划+细分状态）

1.解题思路

由于最多可以进行两次交易，我们可以分出四种交易状态：

• 只进行过一次买操作，记为buy1。
• 进行过一次买操作和一次卖操作，记为sell1。
• 完成一笔交易后，又进行一次买操作，记为buy2。
• 完成了两笔交易，记为sell2。

因为要买入股票，buy1和buy2的初值都是 ，buy1和buy2的初值都是0。状态转移过程中，每一种状态的最大值，要么是对应前一种状态转化而来（buy1卖出股票变为sell1状态，sell1买入股票变为buy2，buy2卖出股票变为sell2），要么保持当前状态。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int n=prices.length;

        //赋初值
        int buy1=-prices[0],sell1=0;
        int buy2=-prices[0], sell2=0;

        for (int i=1;i<n;i++) {
            //状态转移
            buy1=Math.max(buy1,-prices[i]);
            sell1=Math.max(sell1,buy1+prices[i]);
            buy2=Math.max(buy2,sell1-prices[i]);
            sell2=Math.max(sell2,buy2+prices[i]);
        }
        return sell2;

    }
}

3.复杂度分析

• 时间复杂度：只需要遍历一次数组，所以时间复杂度为。
• 空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为。