Greedy stock question

question

-1 is buy operation,
0 represents the hold operation, meaning nothing is bought or sold,
1 represents the sell operation.
You're also given an integer k, which is guaranteed to be even.

So you can change the strategy to choose a range of k consecutive elements.
Set elements of the first half of the chosen range to 0,
Set elements of the second half of the chosen range to 1.

for example,

For rates = [2, 4, 1, 5, 10, 6], strategy = [-1, 1, 0, 1, -1, 0], and k = 4, the output should be solution(rates, strategy, k) = 18.

Before the trades start, the profit is 0;
Day 0: strategy[0] = -1, so the algorithm buys currency at price rates[0] = 2, and the profit becomes 0 - 2 = -2;
Day 1: strategy[1] = 1, so the algorithm sells currency at price rates[1] = 4, and the profit becomes -2 + 4 = 2;
Day 2: strategy[2] = 0, so the algorithm holds currency, and the profit doesn't change;
Day 3: strategy[3] = 1, so the algorithm sells currency at price rates[3] = 5, and the profit becomes 2 + 5 = 7;
Day 4: strategy[4] = -1, so the algorithm buys currency at price rates[4] = 10, and the profit becomes 7 - 10 = -3;
Day 5: strategy[5] = 0, so the algorithm holds currency, and the profit doesn't change;
Thus, the total profit is -3.

We may change exactly k = 4 consecutive elements of the strategy to be equal to [0, 0, 1, 1].

strategy = [0, 0, 1, 1, -1, 0] profit = -4
strategy = [-1, 0, 0, 1, 1, 0] profit = 13
strategy = [-1, 1, 0, 0, 1, 1] profit = 18.
So, the max profit is 18.

solution

i tried brute force attempt. This is a sample impl. But the logic is kinda like backtracking. Instead of calculating the new max profit per strategy, we take the initial profit and "UNDO THE CHANGES" that we initially did and apply the new strategy action.

For example, when the initial strategy was buy (-1) and we want to undo this and hold instead, we need to undo the buy by adding back the money spent.

The second half bit where we want to sell instead of buy is the trickiest. We first need to undo the buy so we add back the money spent. Then, we sell so we add however money we earn (rates[i]) to our profit.

btw we do step 1 cuz initial profit might be the max profit that we have, which is greater if we change it to another strategy.

def solution(rates, strategy, k):
    n = len(rates)
    
    # Step 1: Calculate initial profit
    initial_profit = 0
    for i in range(n):
        if strategy[i] == -1:  # Buy
            initial_profit -= rates[i]
        elif strategy[i] == 1:  # Sell
            initial_profit += rates[i]
    
    # Step 2: Prepare sliding window to track the impact of changing strategy
    max_profit = initial_profit
    
    # Iterate over every possible starting index of the range
    for start in range(n - k + 1):
        # Step 3: Calculate impact of replacing strategy[start:start + k] 
        modified_profit = initial_profit
        
        # First half: make strategy `0` (neutralize buy/sell)
        for i in range(start, start + k // 2):
            if strategy[i] == -1:  # Undo buy
                modified_profit += rates[i]
            elif strategy[i] == 1:  # Undo sell
                modified_profit -= rates[i]
        
        # Second half: make strategy `1` (force sell)
        for i in range(start + k // 2, start + k):
            if strategy[i] == -1:  # Undo buy, then apply sell
                modified_profit += 2 * rates[i]
            elif strategy[i] == 0:  # Apply sell
                modified_profit += rates[i]
        
        # Update max profit
        max_profit = max(max_profit, modified_profit)
    
    return max_profit