發現自己的壞習慣 問題都還沒釐清就開始寫程式 常常寫到最後跟題目要求完全不一樣
之後會強迫自己先花5分鐘徹底詳讀題目
這題卡的比想像中久 腦袋一直想著要用Deivde&Conquer解最後想當然沒解決 還是偷看答案了
(最後有用GPT幫我用DC解給我看 O(NlogN))但時間複雜度還是用線性解比較漂亮O(n)

本日耗時:28mins

121. Best Time to Buy and Sell Stock
     You are given an array prices where prices[i] is the price of a given stock on the ith 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.

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        if (prices.empty()) return 0;

        int minPrice = prices[0];  // 初始化最低價格
        int maxProfit = 0;         // 初始化最大利潤

        // 從第二天開始遍歷每一天的價格
        for (int i = 1; i < prices.size(); i++) {
            // 計算當天賣出的利潤
            int profit = prices[i] - minPrice;

            // 更新最大利潤
            maxProfit = std::max(maxProfit, profit);

            // 更新最低價格
            minPrice = std::min(minPrice, prices[i]);
        }

        return maxProfit;
    }
};