This is an updated version of the last problem. You can buy and sell an unlimited number of times in a period of time. You can buy and sell twice. That makes it a lot more difficult. (Buyers and sellers of stocks with more than three years of experience will choose this option to maximize profits with the minimum number of purchases and sales.)

123 The best time to buy and sell stocks III

Topic:

Given an array, its ith element is the price of a given stock on day I. Design an algorithm to calculate the maximum profit you can make. You can make up to two deals. Note: You can't participate in more than one transaction at a time (you must sell your previous shares before buying again).Copy the code

Example 1:

Input:3.3.5.0.0.3.1.4] output:6Explanation: In no4Day (stock price =0) time to buy, at No6Day (stock price =3), the trade can make a profit3-0 = 3. Then, at No7Day (stock price =1) time to buy, at No8Day (stock price =4), the trade can make a profit4-1 = 3 。
Copy the code

Example 2:

Input:1.2.3.4.5] output:4Explanation: In no1Day (stock price =1) time to buy, at No5Day (stock price =5), the trade can make a profit5-1 = 4. Mind you can't be in the first1Heaven and the first2Buy stocks day after day and sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3:

Input:7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0.Copy the code

The solution is as follows:

  • 1. Since there can only be two trades at most, you can divide the time into two parts and find out the gains made during the two periods of time (so that cross-trading cannot occur) respectively, and add the two together to obtain the maximum profit for two trades at most in this case. To reduce the complexity of the division, we can go back and forth and cache the maximum profit from a single transaction. Then, the maximum transaction that can be obtained from a maximum transaction is calculated backwards, and the sum of the corresponding cache is the maximum profit under a partition.

  • 2. Add the corresponding values at the ith in M1 and M2 to obtain the maximum profit.

The code is as follows:

package com.zhoujian.solutions.didi;
import java.util.Scanner;
/ * * *@author [email protected] 2018/9/9 14:41
 */
public class Stock3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] split = s.split(",");
        int n = split.length;
        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = Integer.parseInt(split[i]);
        }
        int max_profit = maxProfit(prices);
        System.out.println(max_profit);
    }

    private static int maxProfit(int[] prices) {
        int N = prices.length;
        if(N == 0) return 0;
        // Store profits
        int[] M1 = new int[N];
        int[] M2 = new int[N];

        // Traverse from left to right
        int minPrice = prices[0];
        for(int i = 1; i < N; i++){
            minPrice = Math.min(minPrice, prices[i]);
            M1[i] = Math.max(M1[i-1], prices[i]-minPrice);
        }

        // Traverse from right to left
        int maxPrice = prices[N-1];
        for(int i = N-2; i >= 0; i--){
            maxPrice = Math.max(maxPrice, prices[i]);
            M2[i] = Math.max(M2[i+1], maxPrice-prices[i]);
        }
		// Maximize profit
        int best = 0;
        for(int i = 0; i < N; i++){
            best = Math.max(best, M1[i]+M2[i]);
        }
        returnbest; }}Copy the code

The results are as follows:

  • The time complexity is O(n), and the space complexity is O(n).