Best Time to Buy and Sell Stock

Actually, it's never the best time!

Just kidding.

One key point needs to be remembered is that we have to buy in advance before sell (no short trading!). Thus we need to find the minimum element "before" the maximum value.

The first one:

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

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

For this problem, we only need to track the minimum element before the i-th element and let the temporary profit = prices[i] - min. Compare with the exist profit and find the maximum profit.

public class MaxProfit {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
       // int min = Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;
        int profit = 0;
        
        for (int i = 0; i < prices.length; i++)
        {
            min = prices[i] < min ? prices[i] : min;
            profit = (prices[i] - min) > profit ? (prices[i] - min) : profit;
        }
        
        return profit;
    }
}

The second one:

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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

This one is actually even easier. Because there is no limit to the number of transactions (algorithmic trading? ), every time the i-th element is larger than (i - 1)-th element, we can complete the transaction.

public class MaxProfit {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        int diff = 0;
        int profit = 0;
        for (int i = 1; i < prices.length; i++)
        {
            diff = prices[i] - prices[i - 1];
            if (diff > 0)
                profit += diff;
        }
        return profit;
    }
}

The third one (finally! I am so sleepy....-_-):
This one we need to apply DP. Not once, but twice. Given an array of prices, because there are two transactions, we need to find the maximum difference before i-th price and the maximum difference after the i-th price. So we do it twice. First from the beginning of the prices, and second from the end of the prices.

For example,

Given an array:
2, 6, 7, 9, 3, 2, 4, 8

We first compute the maximum profit we can get before the i-th price, using 1D DP, (refer to the first problem).

maxProfit1st:
0, 4, 5, 7, 7, 7, 7, 7

Second, because the second transaction must come after the the first transaction, we need to calculate it from the last element to the first one.
Or we can understand in this way:
total_maximum_profit = maxProfit1st[i] + max_profit_from_i_to_length-1 (maxProfit2nd);

Doing it reversely:

maxProfit2nd
6, 6, 6, 6, 6, 6, 4, 0

So the total_maximum_profit = max(maxProfit1st[i], maxProfit2nd[i]).

public class MaxProfit {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        //First transaction from 0th price to ith price
        int[] maxProfit1st = new int[prices.length];
        int min = prices[0];
        maxProfit1st[0] = 0;
        for (int i = 1; i < maxProfit1st.length; i++)
        {
            min = Math.min(min, prices[i]);
            maxProfit1st[i] = Math.max(prices[i] - min, maxProfit1st[i - 1]);
        }
        //Second transaction from ith price to (length - 1)-th price
        int[] maxProfit2nd = new int[prices.length];
        maxProfit2nd[prices.length - 1] = 0;
        int max = prices[prices.length - 1];
        for (int i = maxProfit2nd.length - 2; i >= 0; i--)
        {
            max = Math.max(max, prices[i]);
            maxProfit2nd[i] = Math.max(max - prices[i], maxProfit2nd[i + 1]);
        }
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++)
        {
            maxProfit = Math.max(maxProfit, maxProfit1st[i] + maxProfit2nd[i]);
        }
        return maxProfit;
    }
}