Leetcode: Best Time to Buy and Sell Stock (8ms)

Best Time to Buy and Sell Stock

My Submissions

Total Accepted: 76857 Total Submissions: 223909 Difficulty: Medium

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Subscribe to see which companies asked this question

Hide Tags

 Array Dynamic Programming

Show Similar Problems

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Using several variables to store the values:

'low'  to store the current lowest point;

'profit' to store the current highest profit;

'slop' to store the up slop and down slop: in order to find the peaks and valleys. 

Note: don't need to store the high points. 

NOTE: some corner cases:

1. the end point in up slop

2.   [1,9 ,0 ,9] -- in such case, when in last 9, slop is still not updated yet. 

/////////////////////////////////////////////////////////////////////////////////

//codes

class Solution {

 public:

        int maxProfit(vector<int>& prices) {

               //input check

               if (prices.size()<2)return 0;

               int low, high, profit, slop;

               if (prices[1]>prices[0]){

                      low = prices[0]; high = prices[1]; slop = 1; profit = prices[1] - prices[0];

               }

               else{

                      low = prices[1]; high = prices[0]; slop = -1; profit = 0;

               }

               for (int i = 2; i<prices.size(); i++){

                      if (i == prices.size() - 1 && prices[i]>prices[i - 1])//slop==1)//last value

                      {

                            low = prices[i - 1]<low ? prices[i - 1] : low;

                            profit = prices[i] - low>profit ? prices[i] - low : profit;

                      }

                      else if (slop == -1 && prices[i]>prices[i - 1])//low point

                      {

                            low = prices[i - 1]<low ? prices[i - 1] : low;

                            slop = 1;

                      }

                      else if (slop == 1 && prices[i]<prices[i - 1])//high point

                      {

                            profit = prices[i - 1] - low>profit ? prices[i - 1] - low : profit;

                            slop = -1;

                      }

                      else continue;

               }

               return profit;

        }

 };

/////////another two methods
/*
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0)return 0;
        //using two loops
        //outter loop swip from i->end
        //inner loop swip from i+1->end
        int profit=0, min=prices[0]+1;
        for(int i=0;i<prices.size();i++){
            if(prices[i]>=min)continue;//skip some unessisary cases
            else min=prices[i];
            for(int j=i+1;j<prices.size();j++){
                if(prices[j]-prices[i]>profit)profit=prices[j]-prices[i];
            }
        }
        return profit;
    }
};
*/


///the third method 
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2)return 0;
        //using two parameters to store the value: profit, min
        int profit=prices[1]-prices[0]>0?prices[1]-prices[0]:0, min=prices[0];
        for(int i=1;i<prices.size();i++){
            if(prices[i]<min)min=prices[i];
            else if (prices[i]-min>profit)profit=prices[i]-min;
        }
        return profit;
    }

};