121. Лучшее время для покупки и продажи акций (Best Time to Buy and Sell Stock)

Задание.

Вам предоставляется массив prices[i], где prices[i] – это цена данной акции на i-й день.

Вы хотите максимизировать свою прибыль, выбрав один день для покупки одной акции и выбрав другой день в будущем для продажи этой акции.

Верните максимальную прибыль, которую вы можете получить от этой транзакции. Если вы не можете получить никакой прибыли, верните 0.

Пример 1.

Входные данные: prices = [7,1,5,3,6,4]

Результат: 5

Пояснение: Покупайте в день 2 (цена = 1) и продавайте в день 5 (цена = 6), прибыль = 6-1 = 5. Обратите внимание, что не разрешается покупка во 2-й день и продажа в 1-й день, потому что вы должны купить перед продажей.

Пример 2.

Входные данные: prices = [7,6,4,3,1]

Результат: 0

Пояснение: В этом случае сделки не совершаются, а максимальная прибыль = 0.

Решение.

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