題目連結: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

法一: Dynamic programming (track min buy value and max profit)

Time complexity: O(n)

   func maxProfit(_ prices: [Int]) -> Int {
        if prices.count == 0 || prices.count == 1 { return 0 }
        var minBuyVal = prices[0]
        var maxProfit = 0
        for price in prices {
            minBuyVal = min(minBuyVal, price)
            maxProfit = max(maxProfit, price - minBuyVal)
        }
        return maxProfit
    }
參考:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/discuss/173309/Swift-easy-simple-solution

https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-121-best-time-to-buy-and-sell-stock/


法二: Brute Force
Time complexity: O(n^2)

    func maxProfit(_ prices: [Int]) -> Int {
        var profit = Array(repeating: 0, count: prices.count)
        for i in 0 ..< prices.count {
        	var max = 0
        	for j in (i+1) ..< prices.count {
        		if profit[j] - profit[i] > max {
        			max = profit[j] - profit[i]
        		}
        	}
        	profit[i] = max
        }
        return profit.max()
    }