DP c++ solution, 8 lines of code


  • 2
    J

    prices = ( p(1), p(2), ... p(N) )

    f'(n) is the approximate max profits of f(n) when ignoring the case f(n-1)

    f(n) is the real max profits

    f(1) = f(0) = 0;
    f'(1) = 0;

    when n>=2

    f'(n) = max{f(n-2), p(n) - p(n-1) + f'(n-1)};

    f(n) = max{f'(n), f(n-1)}

    int maxProfit(vector<int>& prices) {
      if(prices.size() <= 1) return 0;
    
      // store the f(n) and f(n-1)
      int res = 0, res_p = 0;
      // store the f'(n)
      int res_ = 0;
    
      for( unsigned i = 1; i < prices.size(); i++){
        res_ = max(res_p, prices[i] - prices[i-1] + res_);
        res_p = res; // NOTE: transfer the value !!
        res = max(res, res_);
        
      }
      return res;
    }

Log in to reply
 

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