A different view for this problem.


  • 0
    Y

    Firstly , I didn't want to show my code, because it's not important and my code is ugly. haha!

    let's see this problem. wo can easily think of DP, when we in the nth day. there is 3 action we can take. Buy or Sell or Neither. we can use f(n) represent the max profit when we buy at nth day. here problem comes when we try to build the transition function

    1. we can't make sure we can buy at nth day! because we may hold the stock in hands. or we sell the stock yesterday.
    2. we also can't make sure we can sell at nth day!because we my don't have the stock in hands.

    When we think of that , the problem get easier, we must take something to represent the wether we have the stock in hands.

    we take unhold[n] represent the max profit until nth day and we don't have stock in hands.
    hold[n] represent the max profit until nth day and we have stock in hands.

    the transition is much easier.

    unhold[n] = max(unhold[n-1], hold[n-1]+prices[n])
    hold[n] = max(hold[n-1], unhold[n-2]-prices[n) (we have one day calm down)
    

    Now, the problem is almost solved.
    Finally ,I share my ugly code.Sorry for that....

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int N = prices.size();
            if(N == 0)
                return 0;
            if(N == 1)
                return max(prices[1]-prices[0],0);
            vector<int> hold(N),unhold(N);
            hold[0] = -prices[0]; hold[1] = max(-prices[1],-prices[0]);
            unhold[0] = 0; unhold[1] = max(prices[1]-prices[0],0);
            for(int i = 2; i < N; i++){
                hold[i] = max(unhold[i-2]-prices[i], hold[i-1]);
                unhold[i] = max(hold[i-1]+prices[i], unhold[i-1]);
            }
            return max(hold[N-1], unhold[N-1]);
        }
    };
    

Log in to reply
 

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