#121. Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
 

Constraints:

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4

(Brute Force) 1st Try --> SUCCESS

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 1) return 0;
        int ret = 0;
        int mid = prices.size()/2;
        vector<int> left_vector(prices.begin(), prices.begin() + mid);
        vector<int> right_vector(prices.begin() + mid, prices.end());
        auto max_val = max_element(right_vector.begin(), right_vector.end());
        auto min_val = min_element(left_vector.begin(), left_vector.end());
        ret = max(ret, *max_val - *min_val);
        ret = max(ret, maxProfit(left_vector));
        ret = max(ret, maxProfit(right_vector));
        return ret;
    }
};

Applying brute force approach, which is picking buying day and then selling day, recognizes me that the time complexity for this is O(N^2) and that way I can't meet the constraints. So, firstly I tried to make the time complexity into O(NlogN) and the easiest way that came up to my mind is divide and conquer. I used the easiest way to implement this by using recursive function pattern. As you can see, the result was miserable and beats almost nobody..

(Slide Window) 2nd Try --> SUCCESS

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        auto lp = prices.begin();
        auto rp = prices.begin()+1;
        auto ep = prices.end();
        int ret = 0;
        while (rp < ep)
        {
            while(rp != ep && *lp <= *rp)
            {
                ret = max(ret, *rp-*lp);
                rp++;
            }
            lp = rp++;
        }
        return ret;
    }
};

Time complexity can be O(N) by the second solution using slide window approach. And also the code is more simple. Slide window can be used when you have to find kind of max or min things from the array. There should be start and end points and the order of array should be considered. Alright, it seems perfect for applying slide window for this problem. Then how to solve it? Well, I drew a stock charts on my mind and had several thinking experiments. You don't have to think of the buying day when the price of the day is higher than the left point because that day gives you no more profit. So, all I need to do is when I faces the situation that the price of the day goes below than the left point, then moves the pointers and then search the most profit again.