LeetCode 123. Best Time to Buy and Sell Stock III

Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

Do it DP front and back.

public class Solution {
    int[] pre;
    int[] post;
    
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        pre = new int[prices.length];
        post = new int[prices.length];
        
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) min = prices[i];
            pre[i] = prices[i] - min > pre[i-1] ? prices[i] - min : pre[i-1];
        }
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            if (prices[i] > max) max = prices[i];
            post[i] = max - prices[i] > post[i+1] ? max - prices[i] : post[i+1];
        }
        
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            int p = pre[i] + post[i];
            if (p > profit) profit = p;
        }
        return profit;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *