A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast

Problem 1.

Given an array, the ith element is the ith day price of a given stock.

Design an algorithm to calculate the maximum profit you can make. You can complete up to two transactions.

Note: You cannot participate in more than one trade at a time (you must sell your shares before buying again).

Example 1: Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: If you buy on day 4 (stock price = 0) and sell on day 6 (stock price = 3), the exchange will make a profit = 3-0 = 3. Then, by buying on day 7 (stock price = 1) and selling on day 8 (stock price = 4), the exchange makes a profit = 4-1 = 3. Example 2: Input: prices = [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're on multiple trades at once, you have to sell your shares before buying again. Example 3: input: prices = [7,6,4,3,1] output: 0 description: in this case, no transaction has been completed, so the maximum profit is 0. Example 4: Input: prices = [1] Output: 0Copy the code

2.

The best time to buy or sell a stock

The best Time to Buy and Sell stocks II

But there’s an extra state here, which is two transactions at most and you need to enumerate the states of how many transactions are done. See the code for that

class Solution {
    public int maxProfit(int[] prices) {
        int profit[][][] = new int[prices.length][3] [2];    // The second dimension indicates that several transactions have been made, and the third dimension refers to both holding and no stock
        profit[0] [2] [0] = 0;
        profit[0] [2] [1] = -prices[0];
        profit[0] [1] [0] = 0;
        profit[0] [1] [1] = -prices[0];
        for(int i=1; i<prices.length; i++){ // A purchase counts as a transaction; a sale does not count
            profit[i][2] [0] = Math.max(profit[i-1] [2] [0], profit[i-1] [2] [1] + prices[i]);   // Have already made two transactions and have no shares in hand
            profit[i][2] [1] = Math.max(profit[i-1] [2] [1], profit[i-1] [1] [0] - prices[i]);   Profit [I][2][1] - prices[I] = profit[I][2][1] = profit[I] = profit[I
            profit[i][1] [0] = Math.max(profit[i-1] [1] [0], profit[i-1] [1] [1] + prices[i]);
            profit[i][1] [1] = Math.max(profit[i-1] [1] [1], - prices[i]);     // Profit [i-1][0][0]=0, where profit is 0 and no stock has been traded
        }
        return profit[prices.length-1] [2] [0]; }}Copy the code

Similarly, space complexity is reduced

class Solution {
    public int maxProfit(int[] prices) {
		int profit_i20 = 0, profit_i21 = -prices[0], profit_i10 = 0, profit_i11 = -prices[0];
        for(int i=1; i<prices.length; i++){
            profit_i20 = Math.max(profit_i20, profit_i21 + prices[i]);
            profit_i21 = Math.max(profit_i21, profit_i10 - prices[i]);
            profit_i10 = Math.max(profit_i10, profit_i11 + prices[i]);
            profit_i11 = Math.max(profit_i11, -prices[i]);
        }
        returnprofit_i20; }}Copy the code

A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast