LeetCode123. The best time to buy and sell stocks III

This paper is finally updated at 484 Days ago, , The information may have developed or changed .

One 、 Ideas

Find the selection and status

Two 、 problem

Given an array , It's the first i An element is a given stock in the i Sky price .

Design an algorithm to calculate the maximum profit you can get . You can do at most   Two pens   transaction .

Be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.

Example  1:

 Input ：prices = [3,3,5,0,0,3,1,4]
 Output ：6
 explain ： In the  4  God （ Stock price  = 0） Buy when , In the  6  God （ Stock price  = 3） Sell when , The exchange will make a profit  = 3-0 = 3 .
      And then , In the  7  God （ Stock price  = 1） Buy when , In the  8  God  （ Stock price  = 4） Sell when , The exchange will make a profit  = 4-1 = 3 .

Copy

Example 2：

 Input ：prices = [1,2,3,4,5]
 Output ：4
 explain ： In the  1  God （ Stock price  = 1） Buy when , In the  5  God  （ Stock price  = 5） Sell when ,  The exchange will make a profit  = 5-1 = 4 .   
      Notice that you can't be in the  1  Day and day  2  Day after day buying stock , Then sell them .   
      Because it's involved in multiple transactions at the same time , You have to sell the stock before you buy it again .

Copy

Example 3：

 Input ：prices = [7,6,4,3,1] 
 Output ：0 
 explain ： In this case ,  No deal is done ,  So the biggest profit is  0.

Copy

Example 4：

 Input ：prices = [1]
 Output ：0

Copy

Tips ：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 105

Related Topics

• Array
• Dynamic programming

\n

• 691
• 0

3、 ... and 、 Code

public int maxProfit(int[] prices) {
            if (prices.length < 2) {
                return 0;
            }

            int[][][] arr = new int[prices.length][3][2];
            arr[0][2][1] = -prices[0];
            arr[0][2][0] = 0;
            arr[0][1][1] = -prices[0];
            arr[0][1][0] = 0;
            arr[0][0][0] = 0;
            for (int i = 1; i < prices.length; i++) {
                arr[i][2][0] = Math.max(arr[i - 1][2][0], arr[i - 1][2][1] + prices[i]);
                arr[i][2][1] = Math.max(arr[i - 1][2][1], arr[i - 1][1][0] - prices[i]);
                arr[i][1][0] = Math.max(arr[i - 1][1][0], arr[i - 1][1][1] + prices[i]);
                arr[i][1][1] = Math.max(arr[i - 1][1][1], arr[i - 1][0][0] - prices[i]);
            }
            return arr[prices.length - 1][2][0];
        }

Copy

Post Views: 233