Max Strategy Profit
MediumSliding Window · TikTok
You are given two integer arrays of equal length, prices and strategy, and an even integer k.
strategy[i] is the action on day i: -1 means buy, 0 means hold, and 1 means sell. The profit of a strategy is sum(prices[i] * strategy[i]) over all days (buying costs the price, selling earns it). There is no requirement that the strategy be balanced or feasible in any other sense.
You may perform at most one modification: pick exactly k consecutive days and overwrite their actions so that the first k / 2 of those days become 0 (hold) and the last k / 2 become 1 (sell). Days outside the window keep their actions.
Return the maximum possible profit. Not modifying anything is allowed.
Example 1
- Input:
- prices = [3, 6, 2, 7, 5], strategy = [1, -1, 0, -1, 1], k = 4
- Output:
- 15
- Explanation
- The original profit is 3 - 6 - 7 + 5 = -5. Overwriting days 1 to 4 gives
[1, 0, 0, 1, 1]and a profit of 3 + 7 + 5 = 15, the best of the two possible windows.
Example 2
- Input:
- prices = [4, 1, 1, 9], strategy = [1, 1, 1, 1], k = 2
- Output:
- 15
- Explanation
- Every day already sells, for a profit of 15. Any window turns one selling day into a hold (the windows give 11, 14 and 14), so the best choice is not to modify and the answer stays 15.
Example 3
- Input:
- prices = [2, 8], strategy = [-1, -1], k = 2
- Output:
- 8
- Explanation
- The only window is the whole array, turning
[-1, -1]into[0, 1]. Profit goes from -10 to 8.
Constraints
2 <= prices.length == strategy.length <= 10^51 <= prices[i] <= 10^5strategy[i]is-1,0, or12 <= k <= prices.lengthandkis even