Two C++ Methods


  • 0
    C
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
        /**method 1 traversals
            if(prices.empty()) return 0;
            int res = 0;
            int minp = prices[0];
            for(int i=1;i<prices.size();++i){
                if(prices[i]<minp) minp = prices[i];
                if(res < prices[i] - minp) res = prices[i] - minp;
            }
            return res;
        **/
        
        /**method 2 dp*/
            if(prices.empty()) return 0;
            int ps = prices.size();
            int minp[ps];
            int pro[ps];
            minp[0] = prices[0];
            pro[0] = 0;
            for(int i=1;i<ps;++i){
                if(prices[i]-minp[i-1]>pro[i-1]) pro[i] = prices[i]-minp[i-1];
                else pro[i] = pro[i-1];
                if(prices[i]<minp[i-1]) minp[i] = prices[i];
                else minp[i] = minp[i-1];
            }
            return pro[ps-1];
        }
    };
    

Log in to reply
 

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