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).
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- Time: O(n)
- Space: O(n)
The solution overcomplicates a straightforward optimization problem with verbose explanation and heavy prefix-sum machinery, yet still fails to justify key assumptions (like k being even and valid for the input size). Edge cases are completely ignored, and the reasoning is hard to follow because it’s essentially a long restatement of the code rather than a clear derivation. Correct, but unnecessarily convoluted and poorly explained.