Leetcode-309- best time to buy and sell stocks, including freezing period

# LeetCode-309- The best time to buy and sell stocks includes the freezing period

Given an array of integers , Among them the first i Elements represent the i Day's share price .

Design an algorithm to calculate the maximum profit . Under the following constraints , You can do as many deals as you can （ Buy and sell a stock many times ）:

You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）. After sale of shares , You can't buy shares the next day ( That is, the freezing period is 1 God ).

Example 1：

 Input : [1,2,3,0,2]
 Output : 3 
 explain :  The corresponding transaction status is : [ purchase ,  sell ,  Freezing period ,  purchase ,  sell ]

Copy

# Their thinking

For details, see links. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-lab/

# Java Code

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0){
            return 0;
        }
        // State transition diagram ：
        //        holding                 Not holding shares 
        //     -----、    sell     -----、
        //     holding -----↑--------→ Not holding shares ---↑
        //      |
        //      | sell 
        //      | Out 
        //      ↓
        //     Freezing period ( Nothing can be done during this period ) 
        //
        int[][] dp = new int[prices.length][3];
        //dp[i][x] The first i Day in x state （0. Not holding shares ,1. holding ,2. Freezing period ）
        // Not holding shares 
        dp[0][0] = 0;
        // holding 
        dp[0][1] = -prices[0];
        // Freezing period 
        dp[0][2] = 0;
        for(int i = 1;i < prices.length;i++){
            // The first i Tianbu holdings can be transferred from two states ,1. The first i-1 Tianbu shares , I still don't buy stocks today , Keep non shareholding .2. The freezing period is over , But don't buy stocks today .
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]);
            // The first i Tian shareholding can be transferred from two states ,1. The first i-1 Tianbu shares ( Including whether yesterday was a frozen period or yesterday itself did not hold shares ), Buy stocks today .2. The first i-1 Tian Holdings , Not sold today , Maintain shareholding .
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
            // Only the first one i God sold the stock , The first i Genius can enter the freezing period .
            dp[i][2] = dp[i-1][1] + prices[i];
        }
        // Only the last day does not hold shares （ Non shareholding status ） Or it was sold the day before （ Today is the freezing period ） In both cases, money is in hand , The maximum value occurs in both .
        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][2]);
    }
}

Copy