Leetcode 121. Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock :

給定一個數組價格，其中價格 [i] 是給定股票在第 i 天的價格。希望通過選擇一天購買一隻股票並選擇未來的另一天出售該股票來最大化利潤。返回可以從此交易中獲得的最大利潤。 如果無法獲得任何利潤，則返回 0。

Python

解題思路 :

1. 最大獲利 = 目前價錢 – 前面出現的最低價格
2. 計算每個時間段可能出現的最大獲利是多少
3. 如果現在這個時間段的獲利能比之前的最大獲利還大，以新的時間段為最大獲利

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit=0          #獲利
        buy=10001         #題目設定最大價格為10000，以一個更大的值為初值
        for i in range(len(prices)):
            if prices[i]<buy:       # 找最低買點
                buy=prices[i]
            currentprofit=prices[i]-buy   #每個時間段的獲利
            
            if currentprofit>profit:     時間段的獲利是否能有更高的獲利
                profit=currentprofit
                
        return profit

同理 :

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit=0
        buy=10001
        for price in prices:
            if price<buy:
                buy=price
            if profit<price-buy:
                profit=price-buy
        return profit

C++

用了兩個變量 minPrice 和 maxProfit 來分別記錄股票價格的最低點和最大利潤。我們遍歷整個股票價格數組，當發現當前的價格比 minPrice 還要低時，我們將 minPrice 更新為當前價格，否則如果當前價格減去 minPrice 的利潤比 maxProfit 還要大，則更新 maxProfit。

這種算法的時間複雜度為 O(n)，空間複雜度為 O(1)。

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