Skip to content

3980. Best Time To Buy And Sell Stock Using Strategy

Array Sliding Window Prefix Sum

Problem - Best Time To Buy And Sell Stock Using Strategy

Medium

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

  • prices[i] is the price of a given stock on the ith day.
  • strategy[i] represents a trading action on the ith 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.

 

Example 1:

Input: prices = [4,2,8], strategy = [-1,0,1], k = 2

Output: 10

Explanation:

Modification Strategy Profit Calculation Profit
Original [-1, 0, 1] (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 4
Modify [0, 1] [0, 1, 1] (0 × 4) + (1 × 2) + (1 × 8) = 0 + 2 + 8 10
Modify [1, 2] [-1, 0, 1] (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 4

Thus, the maximum possible profit is 10, which is achieved by modifying the subarray [0, 1]​​​​​​​.

Example 2:

Input: prices = [5,4,3], strategy = [1,1,0], k = 2

Output: 9

Explanation:

Modification Strategy Profit Calculation Profit
Original [1, 1, 0] (1 × 5) + (1 × 4) + (0 × 3) = 5 + 4 + 0 9
Modify [0, 1] [0, 1, 0] (0 × 5) + (1 × 4) + (0 × 3) = 0 + 4 + 0 4
Modify [1, 2] [1, 0, 1] (1 × 5) + (0 × 4) + (1 × 3) = 5 + 0 + 3 8

Thus, the maximum possible profit is 9, which is achieved without any modification.

 

Constraints:

  • 2 <= prices.length == strategy.length <= 105
  • 1 <= prices[i] <= 105
  • -1 <= strategy[i] <= 1
  • 2 <= k <= prices.length
  • k is even

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        n = len(prices)
        profit_prefix_sum = [0] * (n + 1)
        price_prefix_sum = [0] * (n + 1)

        for i, (a, b) in enumerate(zip(prices, strategy), 1):
            profit_prefix_sum[i] = profit_prefix_sum[i - 1] + a * b
            price_prefix_sum[i] = price_prefix_sum[i - 1] + a

        result = profit_prefix_sum[-1]
        for i in range(k, n + 1):
            result = max(result, profit_prefix_sum[n] - (profit_prefix_sum[i] - profit_prefix_sum[i - k]) +
                    price_prefix_sum[i] - price_prefix_sum[i - k // 2 ]
                )

        return result

Submission Stats:

  • Runtime: 264 ms (76.83%)
  • Memory: 33.5 MB (92.14%)