Recommended reading: General Solutions to stock problems

In order to better understand and remember, here are my rearranged solutions, each of which is very similar with only a few changes.

121. The best time to buy and sell stocks
    public int maxProfit(int[] prices) {
        int buy = -prices[0]; // Buy on the first day, subtract the purchase price
        int sale = 0; // Sell on the first day, there is no such situation, no profit
        for (int price : prices) {
            buy = Math.max(buy, -price); // Buy, minus the price
            sale = Math.max(sale, buy + price); // Sell. Add the price of the sale to the proceeds of the purchase
        }
        return sale;
    }
Copy the code
122. The best time to buy and sell stocks II
    public int maxProfit(int[] prices) {
        int buy = -prices[0]; // On the first day, deduct the purchase price
        int sale = 0; // Sell on the first day, there is no such situation, no profit
        for (int price : prices) {
            buy = Math.max(buy, sale - price); // Buy, subtract the purchase price from the sale price
            sale = Math.max(sale, buy + price); // Sell. Add the price of the sale to the proceeds of the purchase
        }
        return sale;
    }
Copy the code
123. The best time to buy and sell stocks III
    public int maxProfit(int[] prices) {
        int buy1 = -prices[0]; // Buy on the first day, subtract the purchase price
        int sale1 = 0; // Sell on the first day, there is no such situation, no profit
        int buy2 = -prices[0]; // Buy on the first day, subtract the purchase price
        int sale2 = 0; // Sell on the first day, there is no such situation, no profit
        for (int price : prices) {
            buy1 = Math.max(buy1, -price); // First purchase, minus the purchase price
            sale1 = Math.max(sale1, buy1 + price); // On the first sale, add the sale price to the proceeds from the first purchase
            buy2 = Math.max(buy2, sale1 - price); // For the second purchase, subtract the purchase price from the proceeds of the first sale
            sale2 = Math.max(sale2, buy2 + price); // On the second sale, add the proceeds from the second purchase to the sale price
        }
        return sale2;
    }
Copy the code
188. The best time to buy and sell stocks IV

This is the most difficult of the six problems, and the corresponding solution is the most general

    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (len <= 1) {
            return 0;
        }
        k = Math.min(k, len / 2); // It takes a buy/sell pair to form a gain, and k is meaningless if it exceeds half of the days
        int[] buy = new int[k + 1];
        int[] sale = new int[k + 1];
        Arrays.fill(buy, -prices[0]);
        for (int price : prices) {
            for (int i = 1; i <= k; i++) {
                buy[i] = Math.max(buy[i], sale[i - 1] - price); // Buy, subtract the purchase price from the last sale
                sale[i] = Math.max(sale[i], buy[i] + price); // Sell. Add the price of the sale to the proceeds of the purchase}}return sale[k];
    }
Copy the code
309. The best time to buy or sell stocks includes a freeze period
    public int maxProfit(int[] prices) {
        int buy = -prices[0]; // Buy on the first day, subtract the purchase price
        int sale = 0; // Sell on the first day, there is no such situation, no profit
        int prevSale = 0; // Record the proceeds of the previous sale, starting with 0
        for (int price : prices) {
            buy = Math.max(buy, prevSale - price); // Buy, subtract the purchase price from the previous sale
            prevSale = sale; // Record the proceeds from the previous sale
            sale = Math.max(sale, buy + price); // Sell, add the selling price to the purchase price
        }   
        return sale; 
    }
Copy the code
714. The best time to buy and sell stocks includes fees
    public int maxProfit(int[] prices, int fee) {
        int buy = -prices[0]; // Buy on the first day, subtract the purchase price
        int sale = 0; // Sell on the first day, there is no such situation, no profit
        for (int price : prices) {
            buy = Math.max(buy, sale - price); // Buy, subtract the purchase price from the sale price
            sale = Math.max(sale, buy + price - fee); // Sell, add the selling price to the purchase price and deduct the service fee
        }   
        return sale; 
    }
Copy the code