My solution O(N)


  • 0
    W

    We create array profit, where profit[i] - maximum possible profit for day i (we sell stock not later day i) and variable Max stored maximum value of profit for last days if we have stock (NOT sell last time). If we don't sell stock at day i, profit[i]= profit[i-1]. If we sell stock at day we profit[i]= Max+prices[i]. So, profit[i]= maximum(profit[i-1],Max+prices[i]); Obviously, profit[0]= 0. And we remember about updating Max.

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

    and solution without array. (Memory O(1))

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

  • 2
    D

    I don't think you should hardcode the max value. You should use max integer instead. Also, you don't need O(n) space for this question.


  • 0
    W

    We could use 2 variables instead of array profit, because every time we need only two last values of this array.

    class Solution
    {
    public:
    int maxProfit(vector<int> &prices) {
    if (prices.size()<2) return 0;

      int n= prices.size();
      int pr1,pr2;
      
      pr1= 0;
      int Max= INT_MIN;
      for (int i=1; i<n; i++)
      {
          pr2= max(max(pr1,Max+prices[i]),prices[i]-prices[0]);
          if (pr1-prices[i]>Max) Max= pr1-prices[i];
          pr1= pr2;
      }
      return pr1;
    }
    

    };


  • -1
    D

    I put your solution in OJ and it's not accepted for WA. Please check it.


  • 0
    W

    I have checked once more and get accepted.


  • 0
    D

    Strange thing..It get accepted..
    Everyone, this solution is correct


Log in to reply
 

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