給定每日股票價格陣列
prices，可以多次買賣（但同一時間只能持有一股），求最大利潤。
Example:
Input: prices = [7,1,5,3,6,4] Output: 7（第 2 天買、第 3 天賣 +4，第 4 天買、第 5 天賣 +3）
Intuition
TIP
核心思路：貪心——只要明天比今天貴，今天就買明天就賣。所有上漲段的利潤加起來就是最大利潤。
- 與 LC 121（只能交易一次）不同，這題可以多次交易
- 貪心的正確性：任何一段上漲都可以拆成連續日的小交易累加
- 例如 [1,3,5] 中 1→5 的利潤 4 等於 1→3 (2) + 3→5 (2)
Approaches
1. DP (state machine) — O(n) / O(1)
- Idea: 定義兩個狀態——持有股票
hold和不持有cash，每天更新 - Time:
O(n)- 遍歷一次 - Space:
O(1)- 只用兩個變數
class Solution {
fun maxProfit(prices: IntArray): Int {
var cash = 0 // 不持有股票的最大利潤
var hold = -prices[0] // 持有股票的最大利潤
for (i in 1 until prices.size) {
cash = maxOf(cash, hold + prices[i])
hold = maxOf(hold, cash - prices[i])
}
return cash
}
}⭐ 2. Greedy (sum positive diffs) — O(n) / O(1)
- Idea: 遍歷價格，只要今天比昨天高，就把差值加入利潤
- Time:
O(n)- 一次遍歷 - Space:
O(1)- 只用一個累加器
class Solution {
fun maxProfit(prices: IntArray): Int {
var profit = 0
for (i in 1 until prices.size) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1]
}
}
return profit
}
}Note: Peak-Valley
找到每一個谷底買入、峰頂賣出，概念上更接近「實際交易」。
class Solution {
fun maxProfit(prices: IntArray): Int {
var i = 0
var profit = 0
while (i < prices.size - 1) {
// 找谷底
while (i < prices.size - 1 && prices[i] >= prices[i + 1]) i++
val valley = prices[i]
// 找峰頂
while (i < prices.size - 1 && prices[i] <= prices[i + 1]) i++
profit += prices[i] - valley
}
return profit
}
}🔑 Takeaways
- Pattern: 多次交易的股票問題用貪心最直觀；DP 狀態機是通用解法，可推廣到有冷卻期（LC 309）和手續費（LC 714）
- Key trick: 「累加正差值」的貪心正確性來自：任何連續上漲段的總利潤等於逐日差值之和