Best Time to Buy and Sell Stock using Strategy

main.md

Question

Approach

I first compute the original profit as a baseline. Since I’m allowed at most one modification, I reframe the problem as: what is the maximum additional gain I can get by replacing any length-k subarray with a fixed pattern — first k/2 days contribute 0, last k/2 days contribute +prices[i]. For every possible window of length k, I compute the delta profit: (new contribution of the window) − (original contribution of the window). To do this efficiently, I use prefix sums:

• one prefix sum for the original profit contributions strategy[i] * prices[i]
• one prefix sum for prices, to quickly compute the sum of the last k/2 prices in a window

I slide the window across the array, compute the delta in O(1) per window, and keep the maximum positive delta. The final answer is the original profit plus this maximum gain (or unchanged if all deltas are negative).

Implementation

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        n = len(prices)
        half = k // 2

        base_profit = sum(p * s for p, s in zip(prices, strategy))

        pref_orig = [0] * (n + 1)
        pref_price = [0] * (n + 1)

        for i in range(n):
            pref_orig[i + 1] = pref_orig[i] + strategy[i] * prices[i]
            pref_price[i + 1] = pref_price[i] + prices[i]

        max_gain = 0

        for l in range(n - k + 1):
            r = l + k

            orig_window = pref_orig[r] - pref_orig[l]

            sell_sum = pref_price[l + k] - pref_price[l + half]

            gain = sell_sum - orig_window
            max_gain = max(max_gain, gain)

        return base_profit + max_gain

Complexities

• Time: O(n)
• Space: O(n)

Hi, what edges cases were ignored?