Most Meaningful Variable Naming && Eliminate Confusion C++ code


  • 1
    Y

    I have read many solutions in the discussion, and I spent hours on understanding them. Finally I got the idea.
    I realize we can use more meaningful variable names to smooth the learning curve. In the below code, let's focus on the second part.(I did not optimize it to 1-d array, optimize is trival once you understand the principle.)

    "allPositionClosed"[i][j] matrix means the max profits we have realized at j-th day with at most i trades, and all we hold is just cash, without any opened buy or sell position. at day zero, we started with zero cash position, so this matrix is initialize to zero.

    "oneNakedBuyPosition" means we only hold a single buy position.

    How to update "allPositionClosed"[i][j]? At j-th day, we can choose USE OR NOT USE the j-th price.
    If we do not use j-th price, then we have cash position "allPositionClosed"[i][j-1]", i.e, yesterday's cash position. If we choose to use the j-th price, we must PAIR IT with a previous Naked buy position.(Because we want to exit with cash and without any stocks.)
    oneNakedBuyPosition+prices[j] precisely does this. Here we use "+" because after sell, we keep prices[j] in pocket (remember, buy always lowers our cash position, that's why oneNakedBuyPosition is initialized to -prices[0], indicated exactly by its name, after we open a naked buy, it lowers our cash position to -prices[0].)

    in the equation we update the "oneNakedBuyPosition":

    oneNakedBuyPosition=max(oneNakedBuyPosition,allPositionClosed[0][j-1]-prices[j]);

    allPositionClosed[0][j-1] is the cash position up to k-1 trades, and without use j-th price, then we minus prices[j], this means now we completed k trades, and bought at j-th day, and this lowered our cash position.
    Now we have one naked buy position as indicated by its name, and it's ready to be used to pair to a naked sell position.

        int maxProfit(int k,vector<int>& prices) {
        if(prices.size()<2) return 0;
        if(k>prices.size()/2){
            int totalprofits=0;
            for(int i=1;i<prices.size();i++) totalprofits+=(prices[i]-prices[i-1]>0?prices[i]-prices[i-1]:0);
            return totalprofits;
        }
        vector<vector<int>> allPositionClosed(2,vector<int>(prices.size(),0));
        for(int i=1;i<=k;i++){
            int oneNakedBuyPosition=-prices[0];
            for(int j=1;j<prices.size();j++){
                allPositionClosed[1][j]=max(allPositionClosed[1][j-1],oneNakedBuyPosition+prices[j]);
                oneNakedBuyPosition=max(oneNakedBuyPosition,allPositionClosed[0][j-1]-prices[j]);
            }
            allPositionClosed[0]=allPositionClosed[1];
        }
        return allPositionClosed[1].back();
    }

Log in to reply
 

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