122. 买卖股票的最佳时机 II - Java 动态规划+优化

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

原题地址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

题解

这道题和121. 买卖股票的最佳时机 类似，不同点在于：

• 可以多次买入卖出股票
• 同一时间只能持有一支股票

先考虑一种最容易想的N^2的做法：

设dp[i][0]为在第i天选择卖出股票时的最高利润，dp[i][1]为在第i天选择买入股票时的最高利润

当我们考虑在第i天卖出股票时，由于必须先买入股票再卖出，必然在第0——i-1天中的某一天买入了股票，设我们在第j天买入了股票，则此时的最高利润为：

当我们考虑在第i天买入股票时，由于不能同时持有多支股票，必然在第0——i-1天中的某一天卖出了股票（这里假设第0天卖出股票则收益为0），且此时第i天实际上并没有盈利，设我们在第j天卖出了股票，则此时的最高利润为：

在所有dp的值中取最大值即为最高利润

时间复杂度：O(N^2)

空间复杂度：O(N)

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp=new int[prices.length][2];
        int max=0;
        //0 卖出 1 买入
        for (int i=0;i<prices.length;i++){
            for(int j=0;j<i;j++){
                dp[i][0]=Math.max(dp[i][0],dp[j][1]+prices[i]-prices[j]);
                dp[i][1]=Math.max(dp[i][1],dp[j][0]);
                max=Math.max(max,dp[i][0]);
                max=Math.max(max,dp[i][1]);
            }
        }
        return max;
    }
}

优化：

观察公式可以发现

• 对于dp[i][0]，我们实际上就是在第0——i-1天中寻找买入股票时的最高利润（max(dp[j][1]-prices[j])）
• 对于dp[i][1]，我们实际上就是在第0——i-1天中寻找卖出股票时的最高利润（max(dp[j][0])）

实际上，通过两个max变量维护[0,i]的这两个最值进行滚动即可

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp=new int[prices.length][2];
        int max=0;
        int maxIn=Integer.MIN_VALUE,maxOut=Integer.MIN_VALUE;
        //0 卖出 1 买入
        for (int i=0;i<prices.length;i++){
            if(i!=0){
                dp[i][0]=maxIn+prices[i];
                dp[i][1]=maxOut;
            }else{
                dp[i][0]=0;
                dp[i][1]=0;
            }

            maxIn=Math.max(maxIn,dp[i][1]-prices[i]);
            maxOut=Math.max(maxOut,dp[i][0]);

            max=Math.max(max,dp[i][0]);
            max=Math.max(max,dp[i][1]);

        }
        return max;
    }
}