121. Best Time to Buy and Sell Stock

Solution Brute-force

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

• T:
  $O(N^2)$
• S:
  $O(1)$

Solution - Greedy

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int minCost = INT_MAX, maxProfit = 0;
        for (int price : prices)
        {
            minCost = min(price, minCost);
            maxProfit = max(maxProfit, price - minCost);
        }
        return maxProfit;
    }
};

• T:
  $O(N)$
• S:
  $O(1)$