跳转至

3652. 按策略买卖股票的最佳时机

题目描述

给你两个整数数组 prices 和 strategy，其中：

  • prices[i] 表示第 i 天某股票的价格。
  • strategy[i] 表示第 i 天的交易策略，其中：
    • -1 表示买入一单位股票。
    • 0 表示持有股票。
    • 1 表示卖出一单位股票。

同时给你一个 偶数 整数 k，你可以对 strategy 进行 最多一次 修改。一次修改包括：

  • 选择 strategy 中恰好 k 个 连续 元素。
  • 将前 k / 2 个元素设为 0（持有）。
  • 将后 k / 2 个元素设为 1（卖出）。

利润 定义为所有天数中 strategy[i] * prices[i] 的 总和 。

返回你可以获得的 最大 可能利润。

注意： 没有预算或股票持有数量的限制，因此所有买入和卖出操作均可行，无需考虑过去的操作。

 

示例 1：

输入： prices = [4,2,8], strategy = [-1,0,1], k = 2

输出： 10

解释：

修改 策略 利润计算 利润
原始 [-1, 0, 1] (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 4
修改 [0, 1] [0, 1, 1] (0 × 4) + (1 × 2) + (1 × 8) = 0 + 2 + 8 10
修改 [1, 2] [-1, 0, 1] (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 4

因此，最大可能利润是 10，通过修改子数组 [0, 1] 实现。

示例 2：

输入： prices = [5,4,3], strategy = [1,1,0], k = 2

输出： 9

解释：

修改 策略 利润计算 利润
原始 [1, 1, 0] (1 × 5) + (1 × 4) + (0 × 3) = 5 + 4 + 0 9
修改 [0, 1] [0, 1, 0] (0 × 5) + (1 × 4) + (0 × 3) = 0 + 4 + 0 4
修改 [1, 2] [1, 0, 1] (1 × 5) + (0 × 4) + (1 × 3) = 5 + 0 + 3 8

因此，最大可能利润是 9，无需任何修改即可达成。

 

提示：

  • 2 <= prices.length == strategy.length <= 105
  • 1 <= prices[i] <= 105
  • -1 <= strategy[i] <= 1
  • 2 <= k <= prices.length
  • k 是偶数

解法

方法一：前缀和 + 枚举

我们用一个数组 \(\textit{s}\) 来表示前缀和，其中 \(\textit{s}[i]\) 表示前 \(i\) 天的利润和，即 \(\textit{s}[i] = \sum_{j=0}^{i-1} \textit{prices}[j] \times \textit{strategy}[j]\)。我们还用一个数组 \(\textit{t}\) 来表示前缀和，其中 \(\textit{t}[i]\) 表示前 \(i\) 天的股票价格和，即 \(\textit{t}[i] = \sum_{j=0}^{i-1} \textit{prices}[j]\)。

初始时，最大利润为 \(\textit{s}[n]\)。我们枚举修改的子数组的右端点 \(i\)，则左端点为 \(i-k\)。修改后，子数组内前 \(k/2\) 天的策略变为 \(0\)，后 \(k/2\) 天的策略变为 \(1\)，因此利润变化为：

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

因此，我们可以通过枚举所有可能的 \(i\) 来更新最大利润。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
impl Solution {
    pub fn max_profit(prices: Vec<i32>, strategy: Vec<i32>, k: i32) -> i64 {
        let n: usize = prices.len();
        let k: usize = k as usize;

        let mut s: Vec<i64> = vec![0; n + 1];
        let mut t: Vec<i64> = vec![0; n + 1];

        for i in 1..=n {
            let a: i64 = prices[i - 1] as i64;
            let b: i64 = strategy[i - 1] as i64;
            s[i] = s[i - 1] + a * b;
            t[i] = t[i - 1] + a;
        }

        let mut ans: i64 = s[n];
        for i in k..=n {
            let cur = s[n] - (s[i] - s[i - k]) + (t[i] - t[i - k / 2]);
            if cur > ans {
                ans = cur;
            }
        }

        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public 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++) {
            long a = prices[i - 1];
            long 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++) {
            long cur = s[n] - (s[i] - s[i - k]) + (t[i] - t[i - k / 2]);
            if (cur > ans) {
                ans = cur;
            }
        }

        return ans;
    }
}

评论