Simple DP 8ms Solution for Best Time to Buy and Sell Stock III


  • 17
    C
        int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if(size==0 || size ==1) return 0;
        int profit[size];
        int profit1[size];
        int local_min=prices[0];
        int local_max = prices[size-1];
        int j = size-2;
        int result=0;
        profit[0]=0;
        profit1[size-1] = 0;
        for(int i = 1;i<size+1 && j >=0;i++,j--)
        {
            profit[i] = max(profit[i-1],prices[i]-local_min);
            local_min= min(local_min,prices[i]);
            profit1[j] = max(profit1[j+1],local_max-prices[j]);
            local_max = max(local_max,prices[j]);
        }
        for(int i = 1; i<size; i++)
        {
            result = max(result,profit[i]+profit1[i]);
        }
        return result;
    }
    

    };


  • 0
    A

    Nice. I am struggling with how to maintain the maximum profit. It is nice to concentrate on the middle of the two transitions.


  • 0
    A

    Great answer!


  • 0
    X

    But how you do guarantee the exclusive transactions?


  • 0
    T
    result = max(result,profit[i]+profit1[i]); // i is the guaranteed borderline of the two transactions.

Log in to reply
 

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