A Concise DP Solution in Java


  • 198
    J

    The general idea is DP, while I had to add a "quickSolve" function to tackle some corner cases to avoid TLE.

    DP: t(i,j) is the max profit for up to i transactions by time j (0<=i<=K, 0<=j<=T).

        public int maxProfit(int k, int[] prices) {
            int len = prices.length;
            if (k >= len / 2) return quickSolve(prices);
            
            int[][] t = new int[k + 1][len];
            for (int i = 1; i <= k; i++) {
                int tmpMax =  -prices[0];
                for (int j = 1; j < len; j++) {
                    t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
                    tmpMax =  Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
                }
            }
            return t[k][len - 1];
        }
        
    
        private int quickSolve(int[] prices) {
            int len = prices.length, profit = 0;
            for (int i = 1; i < len; i++)
                // as long as there is a price gap, we gain a profit.
                if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
            return profit;
        }

  • 3
    R

    Awesome solution. I got the idea which has O(k*n^2) time complexity. That's why I got TLE in large test cases. Could you please explore your idea a little bit so that we can have a better understanding on this.


  • 9
    W

    Because buy and sell prices may not be the same, when k>len/2, that means we can do as many transactions as we want. So, in case k>len/2, this problem is same to Best Time to Buy and Sell Stock III.

    t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax) gives us the maximum price when we sell at this price;
    tmpMax = Math.max(tmpMax, t[i - 1][j] - prices[j]) gives us the value when we buy at this price and leave this value for prices[j+1].


  • 85
    A

    Actually,
    tmpMax = Math.max(tmpMax, t[i - 1][j] - prices[j]); - this is kind of misleading
    should be
    tmpMax = Math.max(tmpMax, t[i - 1][j-1] - prices[j]); - by changing to this, it is still acceptable, and easy to understand.

    tmpMax means the maximum profit of just doing at most i-1 transactions, using at most first j-1 prices, and buying the stock at price[j] - this is used for the next loop.


  • 2
    J

    Good point. Modified. Thanks.


  • 0
    C

    int[][] t = new int[k + 1][len]; could be changed to one dimension.


  • 32
    Y

    Here is my cpp solution.Very similar to yours : )

    class Solution {
    public:
        int maxProfit(int k, vector<int> &prices) {
            int size = (int)prices.size();
            if (k==0||size<2) {
                return 0;
            }
            if (k>size/2) {
                int sum = 0;
                for(int i = 1;i < size;i++){
                    if(prices[i] > prices[i-1]){
                        sum += prices[i] - prices[i-1];
                    }
                }
                return sum;
            }
            vector<int> buy(k,INT_MIN);
            vector<int> sell(k,0);
            for (int i=0; i<size; i++) {
                for (int j=k-1; j>=0; j--) {
                    sell[j]=max(sell[j],buy[j]+prices[i]);
                    buy[j]=max(buy[j],(j>0?sell[j-1]:0)-prices[i]);
                }
            }
            return sell[k-1];
        }
    };

  • 0
    R

    if (k > len / 2) => if (k >= len / 2) will work.


  • 0
    V

    I wonder if one can get better than O(k*n) with DP. Without DP, using a fancy heap one can get down to O(n*log(n))


  • 1
    X

    When j = 0, t[i - 1][j - 1] - prices[j] = t[i - 1][-1] - prices[0]. Thus "int tmpMax = t[i - 1][0] - prices[0];" is misleading. I prefer "int tmpMax = 0 - prices[0];", regarding t[i - 1][-1] as 0.


  • 0
    S

    And initial tmpMax could be

    int tmpMax = - prices[0];

    because t[i - 1][0] is always equal to zero.


  • 2
    S

    This solution implies that in each day, 2 transactions can be done (1 sell and 1 buy) which is not mentioned in the problem description. I think this should be added to the problem to eliminate misunderstanding.


  • 0
    M

    what's the meaning of sell[] and buy[]?


  • 0
    Y

    sell[i]/buy[i] is the rest money after sell/buy the stock at most i times. we have zero money at first.


  • 0
    D

    You don't have to really sell at that day. The first time you calculated profit of if you sell at day j, then later you use (that value - day j price + day i price) to calculate what profit you will get if you don't sell at day i but sell later.


  • 0
    C
    This post is deleted!

  • 35
    C

    C++ version, inspired by yulingtianxia

    int maxProfitInf(vector<int> &prices) {
        int buyin = INT_MAX, profit = 0;
        for(auto & price : prices) {
            if(price > buyin) profit += price - buyin;                
            buyin = price;
        }
        return profit;
    }
    
    int maxProfit(int k, vector<int> &prices) {
        if(k == 0 || prices.empty()) return 0;
        // Max profit by k transaction from 0 to i
        const int n = prices.size();        
        if(k >= n / 2) return maxProfitInf(prices);
    
        // balance - the balance with at most j transactions with item 0 to i
        // profit - the profit with at most j transactions with item 0 to i
        vector<int> balance(k + 1, INT_MIN), profit(k + 1);
        
        for(int i = 0; i < n; ++i) {
            for(int j = 1; j <= k; ++j) {
                balance[j] = max(profit[j - 1] - prices[i], balance[j]); // whether to buy at prices[i]
                profit[j] = max(balance[j] + prices[i], profit[j]); // whether to sell at prices[i]
            }
        }
        
        return profit[k];
    }

  • 0
    K

    Nice Solution ~ I would say your answer is much more intuitive ! Really help me have a good understanding on the problem.


  • 1
    R

    My question is how to think of questions like this. I mean how to come up with the solution?


  • 5
    5

    if (k >= len / 2) return quickSolve(prices);
    should this be k >= len-1 ?
    say if the prices is [1,2,3,4] k = 2
    it will pass to quickSolve method, but the quickSolve method will make 3 transactions instead of 2


Log in to reply
 

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