[LeetCode] Best Time to Buy and Sell Stock III (Java)

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).

Analysis

In this problem, we are only allowed to complete at most two transactions. We can use the way we used in “Best Time to Buy and Sell Stock I”. For each i, calculate the maximum profit from o to i, and add them together, finding the maximum profit. But every i will costs $O(n)$. So it will cost $O(n^2)$.

We can use DP to optimize it. Two arrays is needed to save the information. One is to save the maximum profit of (0, i) for every possible position i. And another one is to save the maximum profit of (i, N).

To calculate to arrays, we can go through the array from different direction. For example, to calculate the first array. We start from 0, and try to find the maximum profit until position i.

Code

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0)
            return 0;
        int[] profitUntil = new int[prices.length];
        int[] profitFrom = new int[prices.length];
        //Calculate the profit until i.
        int minValue = prices[0];
        profitUntil[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            minValue = Math.min(minValue, prices[i]);
            profitUntil[i] = Math.max(profitUntil[i - 1], prices[i] - minValue);
        }
        //Calculate the profit from i.
        profitFrom[prices.length - 1] = 0;
        int maxValue = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            maxValue = Math.max(maxValue, prices[i]);
            profitFrom[i] = Math.max(profitFrom[i + 1], maxValue - prices[i]);
        }
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++)
            maxProfit = Math.max(maxProfit, profitUntil[i] + profitFrom[i]);
        return maxProfit;
    }
}

public class Solution {

public int maxProfit(int[] prices) {

if (prices.length == 0)

return 0;

int[] profitUntil = new int[prices.length];

int[] profitFrom = new int[prices.length];

//Calculate the profit until i.

int minValue = prices[0];

profitUntil[0] = 0;

for (int i = 1; i < prices.length; i++) {

minValue = Math.min(minValue, prices[i]);

profitUntil[i] = Math.max(profitUntil[i - 1], prices[i] - minValue);

}

//Calculate the profit from i.

profitFrom[prices.length - 1] = 0;

int maxValue = prices[prices.length - 1];

for (int i = prices.length - 2; i >= 0; i--) {

maxValue = Math.max(maxValue, prices[i]);

profitFrom[i] = Math.max(profitFrom[i + 1], maxValue - prices[i]);

}

int maxProfit = 0;

for (int i = 0; i < prices.length; i++)

maxProfit = Math.max(maxProfit, profitUntil[i] + profitFrom[i]);

return maxProfit;

}

Complexity

The complexity is $O(n)$. We can also combined the third for loop to the second one, but it does not affect the time complexity.

Using this method, we can also calculate the profit if we can complete at most M transactions. For example, if we are allowed to complete 3 transactions, we can divided the array to two parts at position i. In the first part, we will calculate the maximum profit from 0 to i. For the second part, we can treat it as an array that are allowed to use two transactions. We need to calculate the array for all i positions. The complexity will be $O(n^2)$. In conclusion, if we can complete at most M transactions, the complexity is $O(n^{(M+1)/2})$.