首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> C++ 入門

LeetCode 122. Best Time to Buy and Sell Stock II:貪心累加所有正差價

     編輯:C++ 入門

題目

可完成任意次買賣 (賣出後才能再買入),求最大利潤。

貪心洞察

只要明天價格高於今天,就應該今天買入明天賣出。將所有上漲區間拆解為逐日正差價之和:

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) 不影響最優解。

複雜度

  • 時間:O(n) —— 單次遍歷
  • 空間:O(1)
  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved