3652. Best Time to Buy and Sell Stock using Strategy

MediumArrayPrefix SumSliding Window

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given two integer arrays prices and strategy, where:

prices[i] is the price of a given stock on the i-th day.
strategy[i] represents a trading action on the i-th day, where:
- -1 indicates buying one unit of the stock.
- 0 indicates holding the stock.
- 1 indicates selling one unit of the stock.

You are also given an even integer k, and may perform at most one modification to strategy. A modification consists of:

Selecting exactly k consecutive elements in strategy.
Set the first k / 2 elements to 0 (hold).
Set the last k / 2 elements to 1 (sell).

The profit is defined as the sum of strategy[i] * prices[i] across all days.

Return the maximum possible profit you can achieve.

Note: There are no constraints on budget or stock ownership, so all buy and sell operations are feasible regardless of past actions.

In other words, you start with a baseline profit computed from the original strategy array. You then have the option to choose one window of k consecutive days. Within that window, the first half of the days are forced to hold (contributing nothing), while the second half of the days are forced to sell (each contributing its full price). Your goal is to decide whether applying such a modification—and at which position—can yield a higher total profit than leaving the strategy unchanged, and to report the best result possible.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Sliding Window?

This problem maps to Sliding Window through a short path in the full flowchart.

The problem considers a single window of k consecutive days to modify the strategy and maximize profit, using a sliding window or prefix sum to evaluate each position.

Open in Flowchart

Intuition

The first thing to notice is that we are only allowed to make at most one modification, and that modification always affects exactly k consecutive days in the same fixed pattern: the first k / 2 days become 0 (hold), and the last k / 2 days become 1 (sell). This means the only real choice we have is where to place this window (or whether to use it at all).

Since the total profit is just the sum of strategy[i] * prices[i], if we pick a window covering days from i - k to i - 1, only those k days change their contribution. Every other day keeps its original contribution. So instead of recomputing the whole profit for each possible window, we just need to know how the profit changes inside that window.

Let's think about what happens inside a chosen window:

The original contribution of these k days is the sum of strategy[j] * prices[j] over the window. After modification, this original contribution is removed, because the strategy values are overwritten.
The first k / 2 days are set to 0, so they contribute nothing.
The last k / 2 days are set to 1, so each contributes its full price, i.e., the sum of prices[j] over the second half of the window.

This naturally points us toward using prefix sums. If we precompute:

s[i] = the total profit over the first i days using the original strategy,
t[i] = the total of prices over the first i days,

then for a window ending at index i (covering i - k to i - 1):

The original profit we remove is s[i] - s[i - k].
The new profit we add from the selling half is t[i] - t[i - k / 2].

So the change in profit for choosing this window is:

Δ = -(s[i] - s[i - k]) + (t[i] - t[i - k / 2])

The total profit after applying this window becomes s[n] + Δ, which simplifies to s[n] - (s[i] - s[i - k]) + (t[i] - t[i - k / 2]).

With prefix sums ready, computing this for any window takes constant time. We start with the baseline s[n] (the case of making no modification), then enumerate every possible window position by sliding the right endpoint i from k to n, and keep track of the maximum profit seen. This turns what looks like a complex search into a simple linear scan.

Pattern Learn more about Prefix Sum and Sliding Window patterns.

Solution Approach

Solution 1: Prefix Sum + Enumeration

We use an array s to represent the prefix sum of profit, where s[i] is the total profit for the first i days, i.e., s[i] = Σ prices[j] * strategy[j] for j from 0 to i - 1. We also use an array t to represent the prefix sum of stock prices, where t[i] = Σ prices[j] for j from 0 to i - 1.

Step 1: Build the prefix sums.

Let n be the length of prices. We create s and t both of size n + 1, initialized to 0 so that s[0] = 0 and t[0] = 0 serve as the empty-prefix base cases. Then we iterate over each day, using a 1-based index i:

s[i] = s[i - 1] + prices[i - 1] * strategy[i - 1] accumulates the running profit.
t[i] = t[i - 1] + prices[i - 1] accumulates the running price total.

In the code, this is done compactly with enumerate(zip(prices, strategy), 1), where a is the price and b is the strategy value for the current day.

Step 2: Initialize the answer with no modification.

The baseline profit, when we choose not to apply any modification, is simply s[n] (the profit over all n days). We set ans = s[n].

Step 3: Enumerate all possible windows.

We slide the right endpoint i of the window from k to n. For each i, the window covers the days from index i - k to i - 1, which is exactly k consecutive days. Applying the modification changes the total profit as follows:

Remove the original profit of the window: s[i] - s[i - k].
Add the sell-half contribution (the last k / 2 days each selling at full price): t[i] - t[i - k // 2].

So the profit after applying this window is:

s[n] - (s[i] - s[i - k]) + t[i] - t[i - k // 2]

We update ans with the maximum of its current value and this new candidate. Because the prefix sums let us evaluate each window in constant time, the entire enumeration runs in a single pass.

Step 4: Return the result.

After checking every window position (plus the no-modification baseline), ans holds the maximum possible profit, which we return.

Complexity Analysis:

Time complexity: O(n), where n is the length of prices. Building the prefix sums takes O(n), and the enumeration of windows also takes O(n), with each window evaluated in O(1).
Space complexity: O(n), due to the two prefix sum arrays s and t.

Example Walkthrough

Let's use a small concrete example to trace through the Prefix Sum + Enumeration approach.

Input:

prices = [4, 2, 8, 3, 6]
strategy = [-1, 0, 1, -1, 1]
k = 2 (so k / 2 = 1)

Step 0: Understand the baseline.

First, compute the original profit using strategy[i] * prices[i]:

Day `i`	`prices[i]`	`strategy[i]`	Contribution
0	4	-1	-4
1	2	0	0
2	8	1	8
3	3	-1	-3
4	6	1	6

Baseline profit = -4 + 0 + 8 - 3 + 6 = 7.

Step 1: Build the prefix sums.

We build s (prefix profit) and t (prefix price), both of size n + 1 = 6, starting with s[0] = 0 and t[0] = 0.

Walking through with 1-based index i:

`i`	`prices[i-1]`	`strategy[i-1]`	`s[i] = s[i-1] + price * strat`	`t[i] = t[i-1] + price`
1	4	-1	`0 + (-4) = -4`	`0 + 4 = 4`
2	2	0	`-4 + 0 = -4`	`4 + 2 = 6`
3	8	1	`-4 + 8 = 4`	`6 + 8 = 14`
4	3	-1	`4 + (-3) = 1`	`14 + 3 = 17`
5	6	1	`1 + 6 = 7`	`17 + 6 = 23`

So:

s = [0, -4, -4, 4, 1, 7]
t = [0, 4, 6, 14, 17, 23]

Notice s[5] = 7, which matches our baseline profit above.

Step 2: Initialize the answer with no modification.

ans = s[n] = s[5] = 7.

Step 3: Enumerate all possible windows.

We slide the right endpoint i from k = 2 to n = 5. Each window covers days i - k to i - 1, where the first k/2 = 1 day holds and the last k/2 = 1 day sells. The candidate profit formula is:

candidate = s[n] - (s[i] - s[i - k]) + (t[i] - t[i - k // 2])

Here s[n] = 7, k = 2, k // 2 = 1.

Window i = 2 (covers days 0–1; day 0 holds, day 1 sells):

Remove original profit: s[2] - s[0] = -4 - 0 = -4
Add sell-half: t[2] - t[1] = 6 - 4 = 2
candidate = 7 - (-4) + 2 = 13
ans = max(7, 13) = 13

Window i = 3 (covers days 1–2; day 1 holds, day 2 sells):

Remove original profit: s[3] - s[1] = 4 - (-4) = 8
Add sell-half: t[3] - t[2] = 14 - 6 = 8
candidate = 7 - 8 + 8 = 7
ans = max(13, 7) = 13

Window i = 4 (covers days 2–3; day 2 holds, day 3 sells):

Remove original profit: s[4] - s[2] = 1 - (-4) = 5
Add sell-half: t[4] - t[3] = 17 - 14 = 3
candidate = 7 - 5 + 3 = 5
ans = max(13, 5) = 13

Window i = 5 (covers days 3–4; day 3 holds, day 4 sells):

Remove original profit: s[5] - s[3] = 7 - 4 = 3
Add sell-half: t[5] - t[4] = 23 - 17 = 6
candidate = 7 - 3 + 6 = 10
ans = max(13, 10) = 13

Step 4: Return the result.

After examining the baseline and all four window positions, the maximum profit is ans = 13.

Verifying the best choice (i = 2):

The winning window covers days 0–1. After modification, strategy becomes [0, 1, 1, -1, 1]:

Day	`prices`	`strategy`	Contribution
0	4	0	0
1	2	1	2
2	8	1	8
3	3	-1	-3
4	6	1	6

Total = 0 + 2 + 8 - 3 + 6 = 13. ✓

This intuitively makes sense: day 0 originally cost us -4 (a buy at a high price of 4), and by forcing it to hold, we eliminate that loss while turning day 1 into a +2 sell — a net swing that beats every other window and the baseline.

Solution Implementation

1class Solution:
2    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
3        n = len(prices)
4
5        # weighted_prefix[i]: prefix sum of prices[j] * strategy[j] for j in [0, i)
6        # This represents the original profit from the first i elements.
7        weighted_prefix = [0] * (n + 1)
8
9        # price_prefix[i]: prefix sum of prices[j] for j in [0, i)
10        # Used when strategy in the modified window's second half becomes 1.
11        price_prefix = [0] * (n + 1)
12
13        for i, (price, weight) in enumerate(zip(prices, strategy), 1):
14            weighted_prefix[i] = weighted_prefix[i - 1] + price * weight
15            price_prefix[i] = price_prefix[i - 1] + price
16
17        # Baseline answer: profit without applying any modification.
18        ans = weighted_prefix[n]
19
20        # Try every window of size k ending at index i (i.e. covering [i - k, i)).
21        # In this window:
22        #   - The first k // 2 elements have strategy forced to 0 (no contribution).
23        #   - The last k // 2 elements have strategy forced to 1 (contribute price).
24        for i in range(k, n + 1):
25            # Original contribution of the window: weighted_prefix[i] - weighted_prefix[i - k]
26            # New contribution: only the second half [i - k // 2, i) counts,
27            #                   contributing price_prefix[i] - price_prefix[i - k // 2]
28            modified = (
29                weighted_prefix[n]
30                - (weighted_prefix[i] - weighted_prefix[i - k])
31                + (price_prefix[i] - price_prefix[i - k // 2])
32            )
33            ans = max(ans, modified)
34
35        return ans
36

1class Solution {
2    public long maxProfit(int[] prices, int[] strategy, int k) {
3        int n = prices.length;
4
5        // profitPrefix[i]: prefix sum of prices[j] * strategy[j] for j in [0, i)
6        // pricePrefix[i]:  prefix sum of prices[j]               for j in [0, i)
7        long[] profitPrefix = new long[n + 1];
8        long[] pricePrefix = new long[n + 1];
9
10        for (int i = 1; i <= n; i++) {
11            long price = prices[i - 1];
12            long strat = strategy[i - 1];
13            // Accumulate the original profit contribution (cast to long to avoid overflow)
14            profitPrefix[i] = profitPrefix[i - 1] + price * strat;
15            // Accumulate the raw price (used when strategy is forced to 1)
16            pricePrefix[i] = pricePrefix[i - 1] + price;
17        }
18
19        int half = k / 2;
20
21        // Initialize the answer with the profit when no modification is applied
22        long ans = profitPrefix[n];
23
24        // Slide a window of size k; i is the exclusive right boundary, so window is [i - k, i)
25        for (int i = k; i <= n; i++) {
26            // Original profit contributed by the current window [i - k, i)
27            long originalWindowProfit = profitPrefix[i] - profitPrefix[i - k];
28
29            // The second half [i - half, i) now has strategy = 1,
30            // contributing the full price of those elements
31            long boostedSecondHalf = pricePrefix[i] - pricePrefix[i - half];
32
33            // Total profit = base profit
34            //              - original window contribution (first/second halves removed)
35            //              + boosted contribution from the second half
36            long candidate = profitPrefix[n] - originalWindowProfit + boostedSecondHalf;
37
38            ans = Math.max(ans, candidate);
39        }
40
41        return ans;
42    }
43}
44

1class Solution {
2public:
3    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
4        int n = prices.size();
5
6        // prefixProfit[i]: sum of prices[j] * strategy[j] for j in [0, i)
7        // prefixPrice[i] : sum of prices[j]              for j in [0, i)
8        vector<long long> prefixProfit(n + 1, 0);
9        vector<long long> prefixPrice(n + 1, 0);
10
11        for (int i = 1; i <= n; ++i) {
12            long long price = prices[i - 1];
13            long long action = strategy[i - 1];
14            // Accumulate weighted profit (cast avoids int overflow before sum).
15            prefixProfit[i] = prefixProfit[i - 1] + price * action;
16            // Accumulate raw price prefix sum.
17            prefixPrice[i] = prefixPrice[i - 1] + price;
18        }
19
20        // Baseline answer: keep the original strategy untouched.
21        long long ans = prefixProfit[n];
22
23        // Try placing the length-k modification window ending at index i (exclusive).
24        // Inside the window: the first k/2 elements contribute 0,
25        // the second k/2 elements contribute the full price (action = 1).
26        for (int i = k; i <= n; ++i) {
27            // Original profit contributed by this window.
28            long long originalWindow = prefixProfit[i] - prefixProfit[i - k];
29            // New profit: only the second half (full price) counts.
30            long long newWindow = prefixPrice[i] - prefixPrice[i - k / 2];
31            // Total = base profit - removed window + replacement window.
32            ans = max(ans, prefixProfit[n] - originalWindow + newWindow);
33        }
34
35        return ans;
36    }
37};
38

1/**
2 * Computes the maximum profit achievable by optionally applying one modification
3 * window of size k to the trading strategy.
4 *
5 * Base profit is sum(prices[i] * strategy[i]).
6 * Within a chosen contiguous window of size k:
7 *   - the first floor(k/2) days have their strategy forced to 0 (no contribution),
8 *   - the remaining days have their strategy forced to 1 (contribute the raw price).
9 *
10 * @param prices   The price for each day.
11 * @param strategy The strategy multiplier for each day.
12 * @param k        The size of the modification window.
13 * @returns The maximum profit obtainable.
14 */
15function maxProfit(prices: number[], strategy: number[], k: number): number {
16    const n: number = prices.length;
17
18    // prefixWeighted[i] = sum of prices[j] * strategy[j] for j in [0, i)
19    const prefixWeighted: number[] = new Array<number>(n + 1).fill(0);
20    // prefixPrice[i] = sum of prices[j] for j in [0, i)
21    const prefixPrice: number[] = new Array<number>(n + 1).fill(0);
22
23    // Build both prefix-sum arrays in a single pass.
24    for (let i = 1; i <= n; i++) {
25        const price: number = prices[i - 1];
26        const weight: number = strategy[i - 1];
27        prefixWeighted[i] = prefixWeighted[i - 1] + price * weight;
28        prefixPrice[i] = prefixPrice[i - 1] + price;
29    }
30
31    // Start with the base profit assuming no window is modified.
32    let answer: number = prefixWeighted[n];
33
34    // The number of days in the first (zeroed) half of the window.
35    const half: number = Math.floor(k / 2);
36
37    // Try every window of size k ending at index i (covering days [i - k, i)).
38    for (let i = k; i <= n; i++) {
39        // Remove the original weighted contribution of the whole window,
40        // then add back the raw prices for the second half (strategy forced to 1).
41        const candidate: number =
42            prefixWeighted[n]
43            - (prefixWeighted[i] - prefixWeighted[i - k])
44            + (prefixPrice[i] - prefixPrice[i - half]);
45
46        answer = Math.max(answer, candidate);
47    }
48
49    return answer;
50}
51

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array prices. The first loop iterates over all elements to build the prefix sum arrays s and t, taking O(n) time. The second loop runs from k to n, performing constant-time operations in each iteration, which also takes O(n) time. Therefore, the overall time complexity is O(n).
Space Complexity: O(n), where n is the length of the array prices. Two auxiliary prefix sum arrays s and t, each of size n + 1, are used to store cumulative values. Hence, the space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting the No-Modification Baseline

A very common mistake is to assume that applying a modification window is always beneficial, and therefore to only compute the maximum over all windows—without ever considering the option of leaving strategy unchanged.

Why it's wrong: The problem says you may perform at most one modification. If every possible window reduces the profit (for example, when the window's original profit is large and positive, but the forced sell-half prices are small), the best choice is to apply no modification at all. Skipping the baseline would return a value lower than the true optimum.

Buggy code:

# WRONG: starts from negative infinity and forces a window to be chosen
ans = float('-inf')
for i in range(k, n + 1):
    modified = (
        weighted_prefix[n]
        - (weighted_prefix[i] - weighted_prefix[i - k])
        + (price_prefix[i] - price_prefix[i - k // 2])
    )
    ans = max(ans, modified)
return ans

Solution: Always initialize ans with the unmodified profit weighted_prefix[n] (i.e., s[n]) before the enumeration. This guarantees the "do nothing" case is part of the candidate set.

ans = weighted_prefix[n]   # baseline: no modification
for i in range(k, n + 1):
    ...
    ans = max(ans, modified)

Pitfall 2: Off-by-One Errors in Window Indexing

Mixing up 0-based array indexing with 1-based prefix-sum indexing easily produces windows that are shifted by one position or have the wrong size.

Why it's wrong: The prefix arrays are defined so that weighted_prefix[i] covers days [0, i). A window of k days ending at day index i - 1 (inclusive) corresponds to the half-open range [i - k, i). The split point between the hold-half and sell-half is at i - k // 2, so the sell-half is [i - k // 2, i). Using i - k/2 measured from the wrong endpoint, or letting i start below k, leads to negative indices or windows of incorrect length.

Buggy code:

# WRONG: window starts at i = 1, producing negative prefix indices
for i in range(1, n + 1):
    modified = (
        weighted_prefix[n]
        - (weighted_prefix[i] - weighted_prefix[i - k])   # i - k can be negative
        + (price_prefix[i] - price_prefix[i - k // 2])
    )

Solution: Let the loop run for i in range(k, n + 1), so the left boundary i - k is always >= 0. Verify the two halves explicitly:

Hold-half (no contribution): [i - k, i - k // 2) → removed entirely.
Sell-half (full price): [i - k // 2, i) → adds price_prefix[i] - price_prefix[i - k // 2].

A quick sanity check: the sell-half length is i - (i - k // 2) = k // 2, exactly as required.

Pitfall 3: Misapplying the "Hold" Semantics in the Window

Some implementations only add the sell-half prices but forget to first remove the original profit of the entire window (both halves), incorrectly assuming the hold-half is already zero in the original strategy.

Why it's wrong: The original strategy values inside the window could be -1, 0, or 1. After modification, the first half is forced to 0 and the second half to 1. To transition correctly, you must subtract the entire window's original weighted contribution (weighted_prefix[i] - weighted_prefix[i - k]) and then add back only the sell-half's full prices. Subtracting only the hold-half, or only the sell-half, leaves stale original contributions in the total.

Buggy code:

# WRONG: removes only the hold-half, leaving the original sell-half intact
modified = (
    weighted_prefix[n]
    - (weighted_prefix[i - k // 2] - weighted_prefix[i - k])  # only hold-half removed
    + (price_prefix[i] - price_prefix[i - k // 2])
)

Solution: Remove the full window contribution before adding the forced sell-half:

modified = (
    weighted_prefix[n]
    - (weighted_prefix[i] - weighted_prefix[i - k])      # remove entire window
    + (price_prefix[i] - price_prefix[i - k // 2])        # add sell-half at full price
)

This correctly zeroes out the hold-half and replaces the original sell-half actions with the forced 1 (sell) action.

Pitfall 4: Integer Division vs. Float Division for `k / 2`

Using k / 2 (true division) instead of k // 2 (integer division) yields a float, which cannot index a list in Python and will raise a TypeError.

Why it's wrong: Although the problem guarantees k is even (so the mathematical value is the same), Python's / operator always returns a float (e.g., 4 / 2 == 2.0). Indexing price_prefix[i - 2.0] throws an error.

Solution: Always use floor division k // 2 for the split point, ensuring an integer index:

half = k // 2
modified = (
    weighted_prefix[n]
    - (weighted_prefix[i] - weighted_prefix[i - k])
    + (price_prefix[i] - price_prefix[i - half])
)

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don't know

3652. Best Time to Buy and Sell Stock using Strategy

Problem Description

How We Pick the Algorithm

Why Sliding Window?

Intuition

Solution Approach

Solution 1: Prefix Sum + Enumeration

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

Pitfall 1: Forgetting the No-Modification Baseline

Pitfall 2: Off-by-One Errors in Window Indexing

Pitfall 3: Misapplying the "Hold" Semantics in the Window

Pitfall 4: Integer Division vs. Float Division for k / 2

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings

Pitfall 4: Integer Division vs. Float Division for `k / 2`