題目連結: 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()
}