This is the 15th day of my participation in the August More Text Challenge. For details, see:August is more challenging

The title

Given an array of integers where the i-th element represents the i-th day stock price.

Design an algorithm to calculate the maximum profit. You can do as many trades (buying and selling a stock multiple times) as you can under the following constraints:

  • You can’t participate in more than one trade at a time (you have to sell your shares before buying again).
  • After selling the stock, you cannot buy the stock the next day (i.e. the freeze period is 1 day).

The sample

Input: [1,2,3,0,2] output: 3 explanation: the corresponding trade status is: [buy, sell, freeze period, buy, sell]Copy the code

Their thinking

Yeah, the stock it’s here again! 122. The best Time to Buy and Sell stocks II: The best time to buy and Sell stocks So we can do that by adding the freezing period, based on the second problem.

Code implementation

Method one: dynamic programming

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // There is one more freezing period than in the second question
        int[][] dp = new int[n][3];
        // dp[I][0
        dp[0] [0] = -prices[0];
        for(int i = 1; i < n; ++i){
            / / position
            dp[i][0] = Math.max(dp[i - 1] [0], dp[i - 1] [2] - prices[i]);
            / / sell
            dp[i][1] = dp[i - 1] [0] + prices[i];
            / / freezing period
            dp[i][2] = Math.max(dp[i - 1] [1], dp[i - 1] [2]);
        }
        // Return the result, the value range is the empty position state and the frozen state to take the maximum benefit
        return Math.max(dp[n - 1] [1], dp[n - 1] [2]); }}Copy the code

Complexity analysis

  • Time complexity: O(n)O(n)O(n).
  • Space complexity: O(n)O(n)O(n).

Method two: dynamic programming optimization

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int hold = -prices[0], empty = 0, freezing = 0;
        
        for(int i = 1; i < n; ++i){
            int tmp = hold;
            hold = Math.max(hold, freezing - prices[i]);
            freezing = Math.max(freezing, empty);
            empty = tmp + prices[i];
        }

        returnMath.max(empty, freezing); }}Copy the code

Complexity analysis

  • Time complexity: O(n)O(n)O(n).
  • Space complexity: O(1)O(1)O(1).

The last

The article has the bad place that writes, ask big guy people not stingy give instruction, mistake is most can let a person grow, wish I and big guy the distance between shorten gradually!

If you think the article is helpful to you, please like, collect, follow, comment one key four connect support, your support is my creation biggest power!!

Source: leetcode-cn.com/problems/be…