Interview Classic 150 Questions P121 Best Time to Buy and Sell Stock

---

Timeline

Timeline

2025-10-01

init

Array

---

Problem:

P121 Best Time to Buy and Sell Stock

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150

Just maintain two values: the current lowest price and the historical maximum profit. Each time, assume selling today, then find the historical lowest point before today. This historical lowest point does not require extra traversal; it is recorded along the way when considering each day.

#include <climits>

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int max_profit = 0;
        int min_price = prices[0];
        int i = 0;

        for(i = 1; i<n;i++){
            max_profit = std::max(max_profit, prices[i] - min_price); // Each time assume selling the stock on day i.
            min_price = std::min(prices[i], min_price);
        }

        return max_profit;

    }
};