3652. Best Time to Buy and Sell Stock using Strategy

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.

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 <= 10⁵
1 <= prices[i] <= 10⁵
-1 <= strategy[i] <= 1
2 <= k <= prices.length
k is even

Solutions

Solution 1: Prefix Sum + Enumeration

We use an array \(\textit{s}\) to represent the prefix sum, where \(\textit{s}[i]\) is the total profit for the first \(i\) days, i.e., \(\textit{s}[i] = \sum_{j=0}^{i-1} \textit{prices}[j] \times \textit{strategy}[j]\). We also use an array \(\textit{t}\) to represent the prefix sum of stock prices, where \(\textit{t}[i] = \sum_{j=0}^{i-1} \textit{prices}[j]\).

Initially, the maximum profit is \(\textit{s}[n]\). We enumerate the right endpoint \(i\) of the subarray to be modified, with the left endpoint being \(i-k\). After modification, the first \(k/2\) days of the subarray have strategy \(0\), and the last \(k/2\) days have strategy \(1\), so the profit change is:

\[\Delta = -(\textit{s}[i] - \textit{s}[i-k]) + (\textit{t}[i] - \textit{t}[i-k/2])\]

Therefore, we can update the maximum profit by enumerating all possible \(i\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

Python3JavaC++GoTypeScript

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        n = len(prices)
        s = [0] * (n + 1)
        t = [0] * (n + 1)
        for i, (a, b) in enumerate(zip(prices, strategy), 1):
            s[i] = s[i - 1] + a * b
            t[i] = t[i - 1] + a
        ans = s[n]
        for i in range(k, n + 1):
            ans = max(ans, s[n] - (s[i] - s[i - k]) + t[i] - t[i - k // 2])
        return ans

class Solution {
    public long maxProfit(int[] prices, int[] strategy, int k) {
        int n = prices.length;
        long[] s = new long[n + 1];
        long[] t = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            int a = prices[i - 1];
            int b = strategy[i - 1];
            s[i] = s[i - 1] + a * b;
            t[i] = t[i - 1] + a;
        }
        long ans = s[n];
        for (int i = k; i <= n; i++) {
            ans = Math.max(ans, s[n] - (s[i] - s[i - k]) + (t[i] - t[i - k / 2]));
        }
        return ans;
    }
}

class Solution {
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        int n = prices.size();
        vector<long long> s(n + 1), t(n + 1);
        for (int i = 1; i <= n; i++) {
            int a = prices[i - 1];
            int b = strategy[i - 1];
            s[i] = s[i - 1] + a * b;
            t[i] = t[i - 1] + a;
        }
        long long ans = s[n];
        for (int i = k; i <= n; i++) {
            ans = max(ans, s[n] - (s[i] - s[i - k]) + (t[i] - t[i - k / 2]));
        }
        return ans;
    }
};

func maxProfit(prices []int, strategy []int, k int) int64 {
    n := len(prices)
    s := make([]int64, n+1)
    t := make([]int64, n+1)

    for i := 1; i <= n; i++ {
        a := prices[i-1]
        b := strategy[i-1]
        s[i] = s[i-1] + int64(a*b)
        t[i] = t[i-1] + int64(a)
    }

    ans := s[n]
    for i := k; i <= n; i++ {
        ans = max(ans, s[n]-(s[i]-s[i-k])+(t[i]-t[i-k/2]))
    }
    return ans
}

function maxProfit(prices: number[], strategy: number[], k: number): number {
    const n = prices.length;
    const s: number[] = Array(n + 1).fill(0);
    const t: number[] = Array(n + 1).fill(0);

    for (let i = 1; i <= n; i++) {
        const a = prices[i - 1];
        const b = strategy[i - 1];
        s[i] = s[i - 1] + a * b;
        t[i] = t[i - 1] + a;
    }

    let ans = s[n];
    for (let i = k; i <= n; i++) {
        const val = s[n] - (s[i] - s[i - k]) + (t[i] - t[i - Math.floor(k / 2)]);
        ans = Math.max(ans, val);
    }
    return ans;
}

3652. Best Time to Buy and Sell Stock using Strategy

Description

Solutions

Solution 1: Prefix Sum + Enumeration

Comments