可完成任意次買賣 (賣出後才能再買入),求最大利潤。
只要明天價格高於今天,就應該今天買入明天賣出。將所有上漲區間拆解為逐日正差價之和:
profit = Σ max(0, prices[i] - prices[i-1])
等價於買在谷底、賣在波峰,但實現極簡。
class Solution {
public:
int maxProfit(vector& prices) {
int profit = 0;
for (int i = 1; i < prices.size(); ++i)
if (prices[i] > prices[i-1])
profit += prices[i] - prices[i-1];
return profit;
}
};
任何多次交易策略的利潤 = Σ (賣出價 - 買入價)。對於連續上漲段 a < b < c,策略「買 a 賣 c」利潤 = c-a = (b-a)+(c-b),與逐日累加相等。對於波動段,跳過下跌日 (差價≤0) 不影響最優解。