# [121\. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

:::spoiler 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)$
:::

:::spoiler 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)$
:::