Easy understanding and can be easily modified to different situations Java Solution


  • 26
    Z

    The basic idea is to create two tables. hold and unhold.

    hold[i][j] means the maximum profit with at most j transaction for 0 to i-th day. hold means you have a stock in your hand.

    unhold[i][j] means the maximum profit with at most j transaction for 0 to i-th day. unhold means you don't have a stock in your hand.

    The equation is

    hold[i][j] = Math.max(unhold[i-1][j]-prices[i],hold[i-1][j]);

    unhold[i][j] = Math.max(hold[i-1][j-1]+prices[i],unhold[i-1][j]);

    when you sell your stock this is a transaction but when you buy a stock, it is not considered as a full transaction. so this is why the two equation look a little different.

    And we have to initiate hold table when k = 0.

    When the situation is you can not buy a new stock at the same day when you sell it. For example you can only buy a new stock after one day you sell it. The same idea. Another situation is when you have to pay a transaction fee for each transaction, just make a modification when you sell it, So just change the unhold equation a little.

    public class Solution {
        //hold[i][k]  ith day k transaction have stock and maximum profit
        //unhold[i][k] ith day k transaction do not have stock at hand and maximum profit
        public int maxProfit(int k, int[] prices) {
            if(k>prices.length/2) return maxP(prices);
            int[][] hold = new int[prices.length][k+1];
            int[][] unhold = new int[prices.length][k+1];
            hold[0][0] = -prices[0];
            for(int i=1;i<prices.length;i++) hold[i][0] = Math.max(hold[i-1][0],-prices[i]);
            for(int j=1;j<=k;j++) hold[0][j] = -prices[0];
            for(int i=1;i<prices.length;i++){
                for(int j=1;j<=k;j++){
                    hold[i][j] = Math.max(unhold[i-1][j]-prices[i],hold[i-1][j]);
                    unhold[i][j] = Math.max(hold[i-1][j-1]+prices[i],unhold[i-1][j]);
                }
            }
            return Math.max(hold[prices.length-1][k],unhold[prices.length-1][k]);
        }
        public int maxP(int[] prices){
            int res =0;
            for(int i=0;i<prices.length;i++){
                if(i>0 && prices[i] > prices[i-1]){
                    res += prices[i]-prices[i-1];
                }
            }
            return res;
        }
    }

  • 0
    H

    nice dynamic programming function, easy understanding, THX :)


  • 5
    L

    Very nice and generalize solution. This can be extended to more complicated questions.

    Based on your idea, this is the shorter version in Java:

    public int maxProfit(int k, int[] prices) {
        if(k == 0 || prices.length < 2)
            return 0;
        if(k > prices.length / 2)
            return noLimit(prices);
        
        // hold[i][j]: For at most i transactions, the max profit on jth day with a stock in hand.
        // unhold[i][j]: For at most i transactions, the max profit on jth day without a stock in hand
        int[][] hold = new int[k+1][prices.length];
        int[][] unhold = new int[k+1][prices.length];
        for(int i = 1; i <= k; i++) {
            hold[i][0] = -prices[0];
            unhold[i][0] = 0;
            for(int j = 1; j < prices.length; j++) {
                hold[i][j] = Math.max(-prices[j] + unhold[i-1][j], hold[i][j-1]); // Buy or not buy
                unhold[i][j] = Math.max(prices[j] + hold[i][j-1], unhold[i][j-1]); // Sell or not sell
            }
        }
        return unhold[k][prices.length-1];
    }
    private int noLimit(int[] prices) { // Solution from Best Time to Buy and Sell Stock II
        int max = 0;
        for(int i = 0; i < prices.length-1; i++) {
            if(prices[i+1] > prices[i])
                max += prices[i+1] - prices[i];
        }
        return max;
    }
    

    This solution can also be applied to Best Time to Buy and Sell Stock II & III


  • 2
    G

    Nice solution! My solution is similar, but only takes o(k) extra space.

    public class Solution {
        public int maxProfit(int k, int[] prices) {
            if (prices == null || prices.length <= 1 || k == 0) { return 0;}
            if (k >= prices.length / 2) {return unlimited(prices);}
            int[] soldN = new int[k + 1], buyN = new int[k + 1];
            for (int i = 0; i <= k; i++) {
                buyN[i] = Integer.MIN_VALUE;
            }
            for (int i = 0; i < prices.length; i++) {
                for (int j = 1; j <= k; j++) {
                    buyN[j] = Math.max(buyN[j], soldN[j - 1] - prices[i]);
                    soldN[j] = Math.max(soldN[j], buyN[j] + prices[i]);
                }
            }
            return soldN[k];
        }
        
        private int unlimited(int[] prices) {
            int sum = 0;
            for (int i = 0; i < prices.length - 1; i++) {
                sum += prices[i + 1] - prices[i] > 0 ? prices[i + 1] - prices[i] : 0;
            }
            return sum;
        }
    }
    

  • 2
    V

    You can just simply return unhold[prices.length-1][k] instead of Math.max(hold[prices.length-1][k],unhold[prices.length-1][k]).

    unhold[prices.length-1][k] must be greater than or equal to hold[prices.length-1][k]


  • 0
    J

    This will cost O(k * n) space, did you get Memory-Outof-limit errror?


  • 0
    J

    @guangstick could you explain what do soldN and buyN mean ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.