LeetCode 123. Best Time to Buy and Sell Stock III

best-time-to-buy-and-sell-stock-iii.java

/**
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
 *
 * O(n) runtime, O(n) space
 *
 * use the solution for 121. Best Time to Buy and Sell Stock to solve this one
 */

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int maxProfit = 0;
        int minPrice = prices[0]; // the minimum price from the first day to day k-1
        int[] first = new int[prices.length]; // the maximum profit with at most one transaction from the first day to day k
        for (int i = 1; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            first[i] = maxProfit;
            minPrice = Math.min(minPrice, prices[i]);
        }
        maxProfit = 0;
        int maxPrice = prices[prices.length-1]; // the maximum price from day k+1 to the last day
        int[] second = new int[prices.length]; // the maximum profit with at most one transaction from day k to the last day
        for (int i = prices.length - 2; i >= 0; i--) {
            maxProfit = Math.max(maxProfit, maxPrice - prices[i]);
            second[i] = maxProfit;
            maxPrice = Math.max(maxPrice, prices[i]);
        }
        maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, first[i] + second[i]);
        }
        return maxProfit;
    }
}