[LeetCode Road] Best Time to Buy and Sell Stock - Solution/C++

121. Best Time to Buy and Sell Stock

Question:

You are given an array prices where prices[i] is the price of a given stock on the i^th 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:

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.

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

Source code

Version 1

Idea:
It is a brute force algorithm. Each elements as buying day (prices[i])compare the profit with other selling day (prices[j], i < j), so we can get the maximum profit, however, the strategy is very inefficient. (Time Limit Exceeded)

Time complexity: O(n²)
Space complexity: O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty() || prices.size() == 1) return 0;
        int profit = 0;
        for(int i = 0; i < prices.size(); i++){
            int cost = prices[i];
            for(int j = i + 1; j < prices.size(); j++){
                int reward = prices[j];
                int temp = reward - cost;
                if(temp > 0 && temp > profit){
                    profit = temp;
                }
            }
        }
        return profit;
    }
};

Version 2

Idea:
It can use only one loop to implement the algorithm.
minPrice: It want to get the lowest price up to i-th day.
maxProfit: It want to get the max profit up to i-th day.
max(maxProfit, prices[i] - minPrice): It means that the minimum price subtracted from the price of selling day(prices[i]) and choose the large profit.

Time complexity: O(n)
Space complexity: O(1)

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