C++ 7 lines DP


  • 1
    B
    class Solution {
    public:
        int maxProfit(vector<int>& prices, int fee) {
            int size = prices.size();
            vector<int>buy(size+1, INT_MIN);
            vector<int>sell(size+1, 0);
            for(int i = 0; i < size; i++)
            {
                buy[i+1] = max(sell[i] - prices[i], buy[i]);
                sell[i+1] = max(buy[i+1] + prices[i] - fee, sell[i]);
            }
            return sell.back();
        }
    };

  • 0
    T

    Here is Java Version:

    class Solution {
        public int maxProfit(int[] prices, int fee) {
            if(prices==null || prices.length<1){
                return 0;
            }   
            int[] hold = new int[prices.length];
            int[] unhold = new int[prices.length];
            for(int i=0;i<prices.length;i++){
                if(i==0){
                    hold[0]=-prices[i]-fee;
                }else{
                    hold[i]=Math.max(hold[i-1],unhold[i-1]-prices[i]-fee);
                    unhold[i]=Math.max(unhold[i-1],hold[i-1]+prices[i]);
                }
            }
            
            return unhold[prices.length-1];
        }
    }
    

Log in to reply
 

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