ปัญหา: กำหนด Stock Prices หา Max Profit จาก ≤ 2 Transactions (Buy-Sell Pairs)
**Key Insight:** สำหรับ k=2 ใช้ 4 Variables ติดตาม State ได้ใน O(1) Space:
- `first_buy`: Max Profit หลัง Buy ครั้งที่ 1 (Negative = Cost)
- `first_sell`: Max Profit หลัง Sell ครั้งที่ 1
- `second_buy`: Max Profit หลัง Buy ครั้งที่ 2 (รวม Profit ครั้งที่ 1)
- `second_sell`: Max Profit หลัง Sell ครั้งที่ 2 (Final Answer)
การติดตั้ง
class Solution:
def solve(self, prices):
first_buy = first_sell = float('-inf')
second_buy = second_sell = float('-inf')
for price in prices:
first_buy = max(first_buy, -price) # Buy 1: -price
first_sell = max(first_sell, first_buy + price) # Sell 1: first_buy + price
second_buy = max(second_buy, first_sell - price) # Buy 2: first_sell - price
second_sell = max(second_sell, second_buy + price) # Sell 2: second_buy + price
return max(0, first_sell, second_sell)
# Test
ob = Solution()
prices = [2, 6, 3, 4, 2, 9]
print(ob.solve(prices)) # 11 (Buy 2 Sell 6 = 4, Buy 2 Sell 9 = 7, Total = 11)
คำอธิบาย
Initialize: `-inf` เพื่อ Max ได้ถูกต้อง
Iterate ราคาทีละวัน Update 4 States ตามลำดับ (สำคัญ! ต้องตามลำดับนี้)
`first_buy = max(first_buy, -price)`: ซื้อครั้งแรก = -Price
`first_sell = max(first_sell, first_buy + price)`: ขายครั้งแรก = first_buy + Price
`second_buy = max(second_buy, first_sell - price)`: ซื้อครั้งที่สอง = Profit ครั้งแรก - Price
`second_sell = max(second_sell, second_buy + price)`: ขายครั้งที่สอง = Profit รวม
Trace: prices = [2, 6, 3, 4, 2, 9]
Initial: fb=-inf, fs=-inf, sb=-inf, ss=-inf
Price=2:
fb = max(-inf, -2) = -2
fs = max(-inf, -2+2) = 0
sb = max(-inf, 0-2) = -2
ss = max(-inf, -2+2) = 0
Price=6:
fb = max(-2, -6) = -2
fs = max(0, -2+6) = 4 ← Buy 2 Sell 6 = 4
sb = max(-2, 4-6) = -2
ss = max(0, -2+6) = 4
Price=3:
fb = max(-2, -3) = -2
fs = max(4, -2+3) = 4
sb = max(-2, 4-3) = 1 ← Hold 4 Profit, Buy at 3 → Net 1
ss = max(4, 1+3) = 4
Price=4:
fb = -2, fs = 4
sb = max(1, 4-4) = 1
ss = max(4, 1+4) = 5
Price=2:
fb = max(-2, -2) = -2
fs = 4
sb = max(1, 4-2) = 2 ← Better: Hold 4, Buy at 2 → Net 2
ss = max(5, 2+2) = 5
Price=9:
fb = -2, fs = 4
sb = 2
ss = max(5, 2+9) = 11 ← Sell at 9: 2+9=11 ✓
Result: max(0, 4, 11) = 11
Generalization: k Transactions (O(nk) Time, O(k) Space)
def max_profit_k(prices, k):
if k >= len(prices) // 2:
return sum(max(0, prices[i+1]-prices[i]) for i in range(len(prices)-1))
buy = [float('-inf')] * (k + 1)
sell = [0] * (k + 1)
for price in prices:
for j in range(1, k + 1):
buy[j] = max(buy[j], sell[j-1] - price)
sell[j] = max(sell[j], buy[j] + price)
return sell[k]
Complexity
- k=2 Version: O(n) Time, O(1) Space
- General k Version: O(nk) Time, O(k) Space
Edge Cases: Empty Prices → 0, All Decreasing → 0 (ไม่ทำ Transaction)
