LeetCode DayDynamic Programming part8

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
Original Page

Method 1, Greedy Algorithms

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

        int profit = 0;
        int buy = prices[0];
        for(int i=1; i<prices.length; i++ ){
            if(buy>=prices[i]){
                buy = prices[i];
            }else{
                profit = Math.max(profit, prices[i]-buy);
            }
        }
        return profit;
    }



</p>
<p>time O(n) space O(1)</p>
<h2>
  
  
  Method 2 Dynamic Programming
</h2>


<pre class="brush:php;toolbar:false">    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[][] dp = new int[prices.length][2];

        // if we want to own the stock we should pay for the specific price
        dp[0][0] = -prices[0];
        for(int i=1; i<dp.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0]);
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[dp.length-1][1];
    }

time O(n) space O(n)
Dynamic Programming is more general than greedy algorithms because it will not only work for the specific problem.

Method 2.1 (improve the space complexity)

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

        // 2 means we have 2 different status (have owned stock or not )
        int[] dp = new int[2];

        // if we want to own the stock we should pay for the specific price
        dp[0] = -prices[0];
        for(int i=1; i<prices.length; i++){
            dp[1] = Math.max(dp[1], prices[i] + dp[0]);
            dp[0] = Math.max(dp[0], -prices[i]);
        }
        // 
        return dp[1];
    }

Be careful here we should process dp[1] first because it will use the previous dp[0] instead of the updated dp[0].

122. Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

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

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

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

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[i][0] = Math.max(dp[i-1][1]-prices[i], dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][0]+prices[i], dp[i-1][1]);
        }

        return dp[prices.length-1][1];
    }

The rolling array method

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

        int[] dp = new int[2];
        dp[0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[1] = Math.max(dp[0]+prices[i], dp[1]);
            dp[0] = Math.max(dp[1]-prices[i], dp[0]);

        }

        return dp[1];
    }

123. Best Time to Buy and Sell Stock III

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5

    public int maxProfit(int[] prices) {
        int transactions = 2;
        int[][] dp = new int[prices.length][transactions*2+1];
        for(int i=1; i<=transactions; i++){
            dp[0][i*2-1] = -prices[0];
        }

        for(int i=1; i<prices.length; i++){

            dp[i][1] = Math.max(dp[i-1][0]-prices[i], dp[i-1][1]);
            dp[i][2] = Math.max(dp[i-1][1]+prices[i], dp[i-1][2]);
            dp[i][3] = Math.max(dp[i-1][2]-prices[i], dp[i-1][3]);
            dp[i][4] = Math.max(dp[i-1][3]+prices[i], dp[i-1][4]);
        }
        Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);

        return dp[prices.length-1][4];
    }

The above is the detailed content of LeetCode DayDynamic Programming part8. For more information, please follow other related articles on the PHP Chinese website!