Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Changing a length-k strategy window affects only that window's contribution. Its first half becomes zero and its second half becomes one, so the new contribution is simply the sum of prices in the second half. Compare this replacement against the window's original profit.

Approach

Build prefix sums of prices and of strategy[i] * prices[i]. The final strategy-prefix value is the unchanged total; initialize the answer with it because modification is optional.

Enumerate every length-k window by its ending index. Use the strategy prefix sums to find its old contribution and the price prefix sums to find the last k / 2 prices. Evaluate originalTotal - oldWindowContribution + secondHalfPriceSum and maximize the answer.

The even-k constraint makes the halves exact. All outside positions keep their original contributions, so each candidate is evaluated without copying or rewriting the strategy, and choosing no modification remains available.

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        n = len(prices)
        pp = [prices[0]] * n
        ps = [strategy[0] * prices[0]] * n

        for i in range(1, n):
            pp[i] = pp[i - 1] + prices[i]
            ps[i] = ps[i - 1] + (strategy[i] * prices[i])

        res = ps[-1]
        for i in range(k - 1, n):
            curr = ps[i] - (ps[i - k] if i - k >= 0 else 0)
            change = pp[i] - (pp[i - k // 2] if i - k // 2 >= 0 else 0)
            res = max(res, ps[-1] - curr + change)

        return res

Complexity analysis

Let n = prices.length. Time: O(n). Auxiliary space: O(n) for two prefix arrays.