題目：給定一個整數陣列 prices，其中第 i 個元素代表股票在第 i 天的價格

• 不同於 Day 12，這次你可以多次買賣股票（但同一天不能同時買入和賣出），求最大獲利
  

解法一

• 只要有漲就加差額
• 最簡單，直接加總每次漲幅

註解：

• 每天只要股價上升，就把差額加進總獲利
• 就像「買進後隔天馬上賣出」，不必管全局，因為每段上漲都可以賺到

理解：

• 想像你每天觀察，如果明天比今天貴，那今天就買，明天就賣，累積所有小獲利

解法二

• 找低買高賣
• 模擬投資人行為

註解：

• 找到「低谷」買入，再找到「高峰」賣出
• 就像觀察整個價格走勢，決定最佳的「一段段操作」
• 與貪心法結果相同，但寫法更直觀地模擬投資人行為

理解：

• 想像在股市圖表上畫線，低點買，高點賣，每一段漲幅都抓住

解法三

• 狀態轉移（持股/不持股）
• 更正式的解法

註解

• dp[i][0]：第 i 天結束後 沒有持股 的最大獲利
• dp[i][1]：第 i 天結束後 持有股票 的最大獲利
• 遞推公式：
  （1）今天不持股 = max(昨天不持股, 昨天持股 + 今天賣)
  （2）今天持股 = max(昨天持股, 昨天不持股 - 今天買)

理解：

• 像是每天做「兩種選擇」：要不要持股？用動態規劃表記錄所有可能，最後取最大獲利