JAVA DP solution (with explanation) 16 lines in total


  • 0
    T

    Dynamic programming

    we use OPT[k] refers to the maximum profit we can get from first k stocks.
    For a given stock, there are three possible implementations: buy, sell, neither of those two.
    In order to simplify this problem, we can merge buy and neither together.
    1. sell: OPT[k] = max(OPT[i-2]+v(k)-v(i)) (2<=i<k)
    2. not sell: OPT[k] = OPT[k-1]

    public int maxProfit(int[] prices) {
            if (prices.length==0)   return 0;
            int[] profit = new int[prices.length];
            for(int i = 1; i < prices.length; i++){
                profit[i] = profit[i-1];
                for(int j = i-1; j>= 0; j--){
                    if(prices[i] > prices[j]){
                        int temp = 0;
                        if(j-2 > 0) temp = profit[j-2];
                        temp += prices[i]-prices[j];
                        if(temp > profit[i])    profit[i] = temp;
                    }
                }
            }
            return profit[prices.length-1];
        }
    

Log in to reply
 

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