LeetCode122. The best time to buy and sell stocks II

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 Element (s) of a given stock i Sky price .

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

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 : [7,1,5,3,6,4]
 Output : 7
 explain :  In the  2  God （ Stock price  = 1） Buy when , In the  3  God （ Stock price  = 5） Sell when ,  The exchange will make a profit  = 5-1 = 4 .
      And then , In the  4  God （ Stock price  = 3） Buy when , In the  5  God （ Stock price  = 6） Sell when ,  The exchange will make a profit  = 6-3 = 3 .

Copy

Example 2:

 Input : [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 : [7,6,4,3,1]
 Output : 0
 explain :  under these circumstances ,  No deal is done ,  So the biggest profit is  0.

Copy

Tips ：

• 1 <= prices.length <= 3 * 10 ^ 4
• 0 <= prices[i] <= 10 ^ 4

Related Topics

• Greedy Algorithm
• Array

\n

• 1107
• 0

3、 ... and 、 Code

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

            int[][] arr = new int[prices.length][2];
            arr[0][1] = -prices[0];
            arr[0][0] = 0;

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

Copy

Post Views: 317