3652. 按策略買賣股票的最佳時機

思路

題目要求中，最多只會有一次修改， 選取一個大小為k的範圍，將前半權重設定為0，後半設定為1。

定義原先的獲利總和為sum。

我們可以建立兩個固定長度為k的滑動窗口，

• 一個紀錄套用原先權重的獲利original
• 一個紀錄套用更改後權重的獲利changed。 假如套用操作，新的總獲利會是sum - original + changed。

總共有n - k個長度的窗口需要判斷。

程式碼

滑動窗口

class Solution
{
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k)
    {
        int n = prices.size();
        long long res = 0;
        
        // res 初始化: 沒做任何操作
        for(int i = 0; i < n; ++i) {
            res += strategy[i] * prices[i];
        } 
        long long original = 0, changed = 0;
        // original 和 changed 第一個窗口的獲利。
        for(int i = 0; i < k; ++i) {
            original += strategy[i] * prices[i];
            if(i >= k / 2) {
                changed += prices[i];
            }
        }

        long long sum = res;
        // res 判斷第一個窗口套用修改後的獲利
        res = max(res, sum - original + changed);
        for(int i = k; i < n; ++i) { // 後續窗口的獲利計算與判斷
            original += strategy[i] * prices[i] - strategy[i - k] * prices[i - k];
            changed += prices[i] - prices[i - k / 2];
            res = max(res, sum - original + changed);
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$