Tuesday, March 17, 2015

Best time to buy and sell stork - IV


It took me a while to figure out the DP solution.
At each day, either it trades or it doesn't , the maximum profit will be between profits[i][j - 1] and the profit gain from selling at prices[j]. Now we need to the determine the maximum profit before we sell at prices[j], and that comes from transition i - 1 (tmpMax).
Consider we are at transition i - 1 and we just get our maximum profit, now we buy at prices[j] (not the same j as in the last paragraph), the maximum profit reduces to profit[i - 1][j] - prices[j], we compare this profit with the previous tmpMax, if it is smaller than tmpMax, we will not buy the stock at day j and leave the tmpMax as it it.

Since at maximum we can trade prices.length / 2 times, if k is larger than that, we simply use the solution in Best time to buy and sell stork - II to solve the problem.

Update 2016-09-26

Max profit of the day is price at the day - minimum cost of last day if we sell the stock today or last day's profit if we don't.
Minimum cost of the day is the minimum cost of last day if we don't buy the stock or today's price - maximum profit of last transaction if we buy the stock today.

public int maxProfit(int k, int[] prices) {
        if(prices == null || prices.length == 0)
            return 0;
        int len = prices.length;
        if(k >= len / 2)
            return quickSolve(prices);
        int[][] profits = new int[k + 1][len];
        for(int i = 1; i <= k; i++){
            int tmpMax = -prices[0];
            for(int j = 1; j < len; j++){
                profits[i][j] = Math.max(profits[i][j - 1], prices[j] + tmpMax);
                tmpMax = Math.max(tmpMax, profits[i - 1][j] - prices[j]);
            }
        }
        return profits[k][len - 1];
    }
    public int quickSolve(int[] prices){
        int profit = 0;
        for(int i = 1; i < prices.length; i++){
            profit += prices[i] - prices[i - 1] > 0 ? prices[i] - prices[i - 1] : 0;
        }
        return profit;
    }

1 comment: