给你两个整数数组 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：

示例 2：

 

提示：

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

解法一

思路和算法

用 $n$ 表示数组 $\textit{prices}$ 和 $\textit{strategy}$ 的长度。如果不修改策略，则利润是 $\sum_{i = 0}^{n - 1} \textit{prices}[i] \times \textit{strategy}[i]$。修改策略等价于将数组 $\textit{strategy}$ 的一个长度为 $k$ 的子数组替换成前 $\dfrac{k}{2}$ 个元素都是 $0$ 且后 $\dfrac{k}{2}$ 个元素都是 $1$。分别考虑所有的长度为 $k$ 的子数组，即可得到最大利润。

创建两个长度为 $n + 1$ 的前缀和数组 $\textit{pricesPrefixSums}$ 与 $\textit{profitPrefixSums}$，对于 $0 \le i \le n$ 有 $\textit{pricesPrefixSums}[i] = \sum_{j = 0}^{i - 1} \textit{prices}$，$\textit{profitPrefixSums}[i] = \sum_{j = 0}^{i - 1} \textit{prices}[i] \times \textit{strategy}[i]$。计算方法是，从小到大遍历 $0 \le i < n$ 的每个下标 $i$，计算 $\textit{pricesPrefixSums}[i + 1] = \textit{pricesPrefixSums}[i] + \textit{prices}[i]$，$\textit{profitPrefixSums}[i + 1] = \textit{profitPrefixSums}[i] + \textit{prices}[i] \times \textit{strategy}[i]$。计算前缀和数组之后，不修改策略的利润是 $\textit{profitPrefixSums}[n]$。

考虑修改策略的子数组的结束下标 $i$，则 $k - 1 \le i < n$，修改策略的子数组的前后各有一段不修改策略的子数组，三段子数组的利润分别计算如下。

• 下标范围 $[0, i - k]$ 的子数组的利润是 $\textit{profitPrefixSums}[i - k + 1] - \textit{profitPrefixSums}[0]$，该段子数组可能为空。

• 下标范围 $[i + 1, n - 1]$ 的子数组的利润是 $\textit{profitPrefixSums}[n] - \textit{profitPrefixSums}[i + 1]$，该段子数组可能为空。

• 下标范围 $[i - k + 1, i]$ 的子数组的利润是 $\textit{pricesPrefixSums}[i + 1] - \textit{pricesPrefixSums}[i - \dfrac{k}{2} + 1]$。

遍历所有可能的修改策略的子数组的结束下标之后，即可得到最大利润。

代码

###Java

class Solution {
    public long maxProfit(int[] prices, int[] strategy, int k) {
        int n = prices.length;
        long[] pricesPrefixSums = new long[n + 1];
        long[] profitPrefixSums = new long[n + 1];
        for (int i = 0; i < n; i++) {
            pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
            profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
        }
        long maximumProfit = profitPrefixSums[n];
        for (int i = k - 1; i < n; i++) {
            long profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i);
            maximumProfit = Math.max(maximumProfit, profit);
        }
        return maximumProfit;
    }

    public long getSum(long[] prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
}

###C#

public class Solution {
    public long MaxProfit(int[] prices, int[] strategy, int k) {
        int n = prices.Length;
        long[] pricesPrefixSums = new long[n + 1];
        long[] profitPrefixSums = new long[n + 1];
        for (int i = 0; i < n; i++) {
            pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
            profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
        }
        long maximumProfit = profitPrefixSums[n];
        for (int i = k - 1; i < n; i++) {
            long profit = GetSum(profitPrefixSums, 0, i - k) + GetSum(profitPrefixSums, i + 1, n - 1) + GetSum(pricesPrefixSums, i - k / 2 + 1, i);
            maximumProfit = Math.Max(maximumProfit, profit);
        }
        return maximumProfit;
    }

    public long GetSum(long[] prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
}

###C++

class Solution {
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        int n = prices.size();
        vector<long long> pricesPrefixSums(n + 1);
        vector<long long> profitPrefixSums(n + 1);
        for (int i = 0; i < n; i++) {
            pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
            profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
        }
        long long maximumProfit = profitPrefixSums[n];
        for (int i = k - 1; i < n; i++) {
            long long profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i);
            maximumProfit = max(maximumProfit, profit);
        }
        return maximumProfit;
    }

    long long getSum(vector<long long>& prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
};

###Python

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        n = len(prices)
        pricesPrefixSums = [0] * (n + 1)
        profitPrefixSums = [0] * (n + 1)
        for i in range(n):
            pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i]
            profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i]
        maximumProfit = profitPrefixSums[n]

        def getSum(prefixSums: List[int], start: int, end: int) -> int:
            return prefixSums[end + 1] - prefixSums[start]

        for i in range(k - 1, n):
            profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k // 2 + 1, i)
            maximumProfit = max(maximumProfit, profit)
        return maximumProfit

###C

long long getSum(long long* prefixSums, int start, int end) {
    return prefixSums[end + 1] - prefixSums[start];
}

long long maxProfit(int* prices, int pricesSize, int* strategy, int strategySize, int k) {
    long long* pricesPrefixSums = (long long*) malloc(sizeof(long long) * (pricesSize + 1));
    long long* profitPrefixSums = (long long*) malloc(sizeof(long long) * (pricesSize + 1));
    memset(pricesPrefixSums, 0, sizeof(long long) * (pricesSize + 1));
    memset(profitPrefixSums, 0, sizeof(long long) * (pricesSize + 1));
    for (int i = 0; i < pricesSize; i++) {
        pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
        profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
    }
    long long maximumProfit = profitPrefixSums[pricesSize];
    for (int i = k - 1; i < pricesSize; i++) {
        long long profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, pricesSize - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i);
        maximumProfit = fmax(maximumProfit, profit);
    }
    return maximumProfit;
}

###Go

func maxProfit(prices []int, strategy []int, k int) int64 {
    n := len(prices)
    pricesPrefixSums := make([]int64, n + 1)
    profitPrefixSums := make([]int64, n + 1)
    for i := 0; i < n; i++ {
        pricesPrefixSums[i + 1] = pricesPrefixSums[i] + int64(prices[i])
        profitPrefixSums[i + 1] = profitPrefixSums[i] + int64(prices[i] * strategy[i])
    }
    maximumProfit := profitPrefixSums[n]
    for i := k - 1; i < n; i++ {
        profit := getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i)
        maximumProfit = max(maximumProfit, profit)
    }
    return maximumProfit
}

func getSum(prefixSums []int64, start int, end int) int64 {
    return prefixSums[end + 1] - prefixSums[start]
}

###JavaScript

var maxProfit = function(prices, strategy, k) {
    let n = prices.length;
    let pricesPrefixSums = new Array(n + 1).fill(0);
    let profitPrefixSums = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
        profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
    }
    let maximumProfit = profitPrefixSums[n];
    for (let i = k - 1; i < n; i++) {
        let profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i);
        maximumProfit = Math.max(maximumProfit, profit);
    }
    return maximumProfit;
};

var getSum = function(prefixSums, start, end) {
    return prefixSums[end + 1] - prefixSums[start];
};

###TypeScript

function maxProfit(prices: number[], strategy: number[], k: number): number {
    let n = prices.length;
    let pricesPrefixSums = new Array(n + 1).fill(0);
    let profitPrefixSums = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
        profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
    }
    let maximumProfit = profitPrefixSums[n];
    for (let i = k - 1; i < n; i++) {
        let profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i);
        maximumProfit = Math.max(maximumProfit, profit);
    }
    return maximumProfit;
};

function getSum(prefixSums: number[], start: number, end: number): number {
    return prefixSums[end + 1] - prefixSums[start];
};

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{prices}$ 和 $\textit{strategy}$ 的长度。计算两个前缀和数组的时间是 $O(n)$，遍历所有可能的修改策略的子数组的结束下标的时间是 $O(n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{prices}$ 和 $\textit{strategy}$ 的长度。两个前缀和数组的空间是 $O(n)$。

解法二

思路和算法

首先计算不修改策略的利润，然后使用长度为 $k$ 的定长滑动窗口遍历数组 $\textit{prices}$ 和 $\textit{strategy}$，计算每个滑动窗口对于利润的变化值。

首个滑动窗口的下标范围是 $[0, k - 1]$，对应的利润变化值是 $\textit{delta} = -\sum_{i = 0}^{k - 1} \textit{prices}[i] \times \textit{strategy}[i] + \sum_{i = \frac{k}{2}}^{k - 1} \textit{prices}[i]$。从小到大遍历 $k \le i < n$ 的每个下标 $i$，当滑动窗口的下标范围从 $[i - k, i - 1]$ 变成 $[i - k + 1, i]$ 时，$\textit{delta}$ 的改变如下。

• 下标 $i - k$ 移出滑动窗口，因此按照不修改策略计算，将 $\textit{delta}$ 的值增加 $\textit{prices}[i - k] \times \textit{strategy}[i - k]$。

• 下标 $i - \dfrac{k}{2}$ 在修改策略的下标范围中从卖出变成持有，因此将 $\textit{delta}$ 的减少 $\textit{prices}[i - \dfrac{k}{2}]$。

• 下标 $i$ 移入滑动窗口，因此按照修改策略的卖出计算，将 $\textit{delta}$ 的值增加 $\textit{prices}[i] - \textit{prices}[i] \times \textit{strategy}[i]$。

对于每个 $\textit{delta}$ 都需要更新最大利润，遍历结束之后即可得到最大利润。

代码

###Java

class Solution {
    public long maxProfit(int[] prices, int[] strategy, int k) {
        long profit = 0;
        int n = prices.length;
        for (int i = 0; i < n; i++) {
            profit += prices[i] * strategy[i];
        }
        long maximumProfit = profit;
        long delta = 0;
        for (int i = 0; i < k; i++) {
            delta -= prices[i] * strategy[i];
            if (i >= k / 2) {
                delta += prices[i];
            }
        }
        maximumProfit = Math.max(maximumProfit, profit + delta);
        for (int i = k; i < n; i++) {
            delta += prices[i - k] * strategy[i - k];
            delta -= prices[i - k / 2];
            delta += prices[i] - prices[i] * strategy[i];
            maximumProfit = Math.max(maximumProfit, profit + delta);
        }
        return maximumProfit;
    }
}

###C#

public class Solution {
    public long MaxProfit(int[] prices, int[] strategy, int k) {
        long profit = 0;
        int n = prices.Length;
        for (int i = 0; i < n; i++) {
            profit += prices[i] * strategy[i];
        }
        long maximumProfit = profit;
        long delta = 0;
        for (int i = 0; i < k; i++) {
            delta -= prices[i] * strategy[i];
            if (i >= k / 2) {
                delta += prices[i];
            }
        }
        maximumProfit = Math.Max(maximumProfit, profit + delta);
        for (int i = k; i < n; i++) {
            delta += prices[i - k] * strategy[i - k];
            delta -= prices[i - k / 2];
            delta += prices[i] - prices[i] * strategy[i];
            maximumProfit = Math.Max(maximumProfit, profit + delta);
        }
        return maximumProfit;
    }
}

###C++

class Solution {
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        long long profit = 0;
        int n = prices.size();
        for (int i = 0; i < n; i++) {
            profit += prices[i] * strategy[i];
        }
        long long maximumProfit = profit;
        long long delta = 0;
        for (int i = 0; i < k; i++) {
            delta -= prices[i] * strategy[i];
            if (i >= k / 2) {
                delta += prices[i];
            }
        }
        maximumProfit = max(maximumProfit, profit + delta);
        for (int i = k; i < n; i++) {
            delta += prices[i - k] * strategy[i - k];
            delta -= prices[i - k / 2];
            delta += prices[i] - prices[i] * strategy[i];
            maximumProfit = max(maximumProfit, profit + delta);
        }
        return maximumProfit;
    }
};

###Python

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        profit = 0
        n = len(prices)
        for i in range(n):
            profit += prices[i] * strategy[i]
        maximumProfit = profit
        delta = 0
        for i in range(k):
            delta -= prices[i] * strategy[i]
            if i >= k // 2:
                delta += prices[i]
        maximumProfit = max(maximumProfit, profit + delta)
        for i in range(k, n):
            delta += prices[i - k] * strategy[i - k]
            delta -= prices[i - k // 2]
            delta += prices[i] - prices[i] * strategy[i]
            maximumProfit = max(maximumProfit, profit + delta)
        return maximumProfit

###C

long long maxProfit(int* prices, int pricesSize, int* strategy, int strategySize, int k) {
    long long profit = 0;
    for (int i = 0; i < pricesSize; i++) {
        profit += prices[i] * strategy[i];
    }
    long long maximumProfit = profit;
    long long delta = 0;
    for (int i = 0; i < k; i++) {
        delta -= prices[i] * strategy[i];
        if (i >= k / 2) {
            delta += prices[i];
        }
    }
    maximumProfit = fmax(maximumProfit, profit + delta);
    for (int i = k; i < pricesSize; i++) {
        delta += prices[i - k] * strategy[i - k];
        delta -= prices[i - k / 2];
        delta += prices[i] - prices[i] * strategy[i];
        maximumProfit = fmax(maximumProfit, profit + delta);
    }
    return maximumProfit;
}

###Go

func maxProfit(prices []int, strategy []int, k int) int64 {
    profit := int64(0)
    n := len(prices)
    for i := 0; i < n; i++ {
        profit += int64(prices[i] * strategy[i])
    }
    maximumProfit := profit
    delta := int64(0)
    for i := 0; i < k; i++ {
        delta -= int64(prices[i] * strategy[i])
        if i >= k / 2 {
            delta += int64(prices[i])
        }
    }
    maximumProfit = max(maximumProfit, profit + delta)
    for i := k; i < n; i++ {
        delta += int64(prices[i - k] * strategy[i - k])
        delta -= int64(prices[i - k / 2])
        delta += int64(prices[i] - prices[i] * strategy[i])
        maximumProfit = max(maximumProfit, profit + delta)
    }
    return maximumProfit
}

###JavaScript

var maxProfit = function(prices, strategy, k) {
    let profit = 0;
    let n = prices.length;
    for (let i = 0; i < n; i++) {
        profit += prices[i] * strategy[i];
    }
    let maximumProfit = profit;
    let delta = 0;
    for (let i = 0; i < k; i++) {
        delta -= prices[i] * strategy[i];
        if (i >= k / 2) {
            delta += prices[i];
        }
    }
    maximumProfit = Math.max(maximumProfit, profit + delta);
    for (let i = k; i < n; i++) {
        delta += prices[i - k] * strategy[i - k];
        delta -= prices[i - k / 2];
        delta += prices[i] - prices[i] * strategy[i];
        maximumProfit = Math.max(maximumProfit, profit + delta);
    }
    return maximumProfit;
};

###TypeScript

function maxProfit(prices: number[], strategy: number[], k: number): number {
    let profit = 0;
    let n = prices.length;
    for (let i = 0; i < n; i++) {
        profit += prices[i] * strategy[i];
    }
    let maximumProfit = profit;
    let delta = 0;
    for (let i = 0; i < k; i++) {
        delta -= prices[i] * strategy[i];
        if (i >= k / 2) {
            delta += prices[i];
        }
    }
    maximumProfit = Math.max(maximumProfit, profit + delta);
    for (let i = k; i < n; i++) {
        delta += prices[i - k] * strategy[i - k];
        delta -= prices[i - k / 2];
        delta += prices[i] - prices[i] * strategy[i];
        maximumProfit = Math.max(maximumProfit, profit + delta);
    }
    return maximumProfit;
};

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{prices}$ 和 $\textit{strategy}$ 的长度。计算不修改策略的利润的时间是 $O(n)$，使用滑动窗口遍历数组的时间是 $O(n)$。

• 空间复杂度：$O(1)$。

拓展问题

问题描述

原始问题只有计算最大利润，在原始问题的基础上，可以提出拓展问题：当利润最大时，是否应修改策略，如果修改策略则应如何修改策略？如果有多种方案，返回其中任意一种。

解法分析

原始问题的两种解法都是首先计算不修改策略的利润，然后分别计算每个长度为 $k$ 的子数组修改策略的利润，得到最大利润。可以在维护最大利润的同时维护修改策略的子数组的起始下标，即可计算最大利润对应的修改策略的子数组。

初始时，修改策略的子数组的起始下标是 $-1$，表示不修改策略。遍历过程中，如果遇到更大利润，则更新修改策略的子数组的起始下标。遍历结束之后，即可得到最大利润对应的修改策略的子数组的起始下标。由于修改策略的子数组长度 $k$ 给定，因此得到修改策略的子数组的起始下标之后，即可得到修改策略的子数组的下标范围。

代码

下面的代码为解法一对应的实现，返回值是下标，表示利润最大时的修改策略的子数组的起始下标，如果不修改策略的利润最大则返回值是 $-1$。

###Java

class Solution {
    public int maxProfit(int[] prices, int[] strategy, int k) {
        int n = prices.length;
        long[] pricesPrefixSums = new long[n + 1];
        long[] profitPrefixSums = new long[n + 1];
        for (int i = 0; i < n; i++) {
            pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
            profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
        }
        long maximumProfit = profitPrefixSums[n];
        int modifyIndex = -1;
        for (int i = k - 1; i < n; i++) {
            long profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i);
            if (profit > maxProfit) {
                maxProfit = profit;
                modifyIndex = i - k + 1;
            }
        }
        return modifyIndex;
    }

    public long getSum(long[] prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
}

###C#

public class Solution {
    public int MaxProfit(int[] prices, int[] strategy, int k) {
        int n = prices.Length;
        long[] pricesPrefixSums = new long[n + 1];
        long[] profitPrefixSums = new long[n + 1];
        for (int i = 0; i < n; i++) {
            pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
            profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
        }
        long maximumProfit = profitPrefixSums[n];
        int modifyIndex = -1;
        for (int i = k - 1; i < n; i++) {
            long profit = GetSum(profitPrefixSums, 0, i - k) + GetSum(profitPrefixSums, i + 1, n - 1) + GetSum(pricesPrefixSums, i - k / 2 + 1, i);
            if (profit > maxProfit) {
                maxProfit = profit;
                modifyIndex = i - k + 1;
            }
        }
        return modifyIndex;
    }

    public long GetSum(long[] prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
}

###C++

class Solution {
public:
    int maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        int n = prices.size();
        vector<long long> pricesPrefixSums(n + 1);
        vector<long long> profitPrefixSums(n + 1);
        for (int i = 0; i < n; i++) {
            pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
            profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
        }
        long long maximumProfit = profitPrefixSums[n];
        int modifyIndex = -1;
        for (int i = k - 1; i < n; i++) {
            long long profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i);
            if (profit > maxProfit) {
                maxProfit = profit;
                modifyIndex = i - k + 1;
            }
        }
        return modifyIndex;
    }

    long long getSum(vector<long long>& prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
};

###Python

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        n = len(prices)
        pricesPrefixSums = [0] * (n + 1)
        profitPrefixSums = [0] * (n + 1)
        for i in range(n):
            pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i]
            profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i]
        maximumProfit = profitPrefixSums[n]
        modifyIndex = -1

        def getSum(prefixSums: List[int], start: int, end: int) -> int:
            return prefixSums[end + 1] - prefixSums[start]

        for i in range(k - 1, n):
            profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k // 2 + 1, i)
            if profit > maxProfit:
                maxProfit = profit
                modifyIndex = i - k + 1
        return modifyIndex

###C

long long getSum(long long* prefixSums, int start, int end) {
    return prefixSums[end + 1] - prefixSums[start];
}

int maxProfit(int* prices, int pricesSize, int* strategy, int strategySize, int k) {
    long long* pricesPrefixSums = (long long*) malloc(sizeof(long long) * (pricesSize + 1));
    long long* profitPrefixSums = (long long*) malloc(sizeof(long long) * (pricesSize + 1));
    memset(pricesPrefixSums, 0, sizeof(long long) * (pricesSize + 1));
    memset(profitPrefixSums, 0, sizeof(long long) * (pricesSize + 1));
    for (int i = 0; i < pricesSize; i++) {
        pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
        profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
    }
    long long maximumProfit = profitPrefixSums[pricesSize];
    int modifyIndex = -1;
    for (int i = k - 1; i < pricesSize; i++) {
        long long profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, pricesSize - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i);
        if (profit > maximumProfit) {
            maximumProfit = profit;
            modifyIndex = i - k + 1;
        }
    }
    return modifyIndex;
}

###Go

func maxProfit(prices []int, strategy []int, k int) int {
    n := len(prices)
    pricesPrefixSums := make([]int64, n + 1)
    profitPrefixSums := make([]int64, n + 1)
    for i := 0; i < n; i++ {
        pricesPrefixSums[i + 1] = pricesPrefixSums[i] + int64(prices[i])
        profitPrefixSums[i + 1] = profitPrefixSums[i] + int64(prices[i] * strategy[i])
    }
    maximumProfit := profitPrefixSums[n]
    modifyIndex := -1
    for i := k - 1; i < n; i++ {
        profit := getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i)
        if profit > maximumProfit {
            maximumProfit = profit
            modifyIndex = i - k + 1
        }
    }
    return modifyIndex
}

func getSum(prefixSums []int64, start int, end int) int64 {
    return prefixSums[end + 1] - prefixSums[start]
}

###JavaScript

var maxProfit = function(prices, strategy, k) {
    let n = prices.length;
    let pricesPrefixSums = new Array(n + 1).fill(0);
    let profitPrefixSums = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
        profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
    }
    let maximumProfit = profitPrefixSums[n];
    let modifyIndex = -1;
    for (let i = k - 1; i < n; i++) {
        let profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i);
        if (profit > maximumProfit) {
            maximumProfit = profit;
            modifyIndex = i - k + 1;
        }
    }
    return modifyIndex;
};

var getSum = function(prefixSums, start, end) {
    return prefixSums[end + 1] - prefixSums[start];
};

###TypeScript

function maxProfit(prices: number[], strategy: number[], k: number): number {
    let n = prices.length;
    let pricesPrefixSums = new Array(n + 1).fill(0);
    let profitPrefixSums = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        pricesPrefixSums[i + 1] = pricesPrefixSums[i] + prices[i];
        profitPrefixSums[i + 1] = profitPrefixSums[i] + prices[i] * strategy[i];
    }
    let maximumProfit = profitPrefixSums[n];
    let modifyIndex = -1;
    for (let i = k - 1; i < n; i++) {
        let profit = getSum(profitPrefixSums, 0, i - k) + getSum(profitPrefixSums, i + 1, n - 1) + getSum(pricesPrefixSums, i - k / 2 + 1, i);
        if (profit > maximumProfit) {
            maximumProfit = profit;
            modifyIndex = i - k + 1;
        }
    }
    return modifyIndex;
};

function getSum(prefixSums: number[], start: number, end: number): number {
    return prefixSums[end + 1] - prefixSums[start];
};

下面的代码为解法二对应的实现，返回值是下标，表示利润最大时的修改策略的子数组的起始下标，如果不修改策略的利润最大则返回值是 $-1$。

###Java

class Solution {
    public int maxProfit(int[] prices, int[] strategy, int k) {
        long profit = 0;
        int n = prices.length;
        for (int i = 0; i < n; i++) {
            profit += prices[i] * strategy[i];
        }
        long maximumProfit = profit;
        int modifyIndex = -1;
        long delta = 0;
        for (int i = 0; i < k; i++) {
            delta -= prices[i] * strategy[i];
            if (i >= k / 2) {
                delta += prices[i];
            }
        }
        if (profit + delta > maximumProfit) {
            maximumProfit = profit + delta;
            modifyIndex = 0;
        }
        for (int i = k; i < n; i++) {
            delta += prices[i - k] * strategy[i - k];
            delta -= prices[i - k / 2];
            delta += prices[i] - prices[i] * strategy[i];
            if (profit + delta > maximumProfit) {
                maximumProfit = profit + delta;
                modifyIndex = i - k + 1;
            }
        }
        return modifyIndex;
    }
}

###C#

public class Solution {
    public int MaxProfit(int[] prices, int[] strategy, int k) {
        long profit = 0;
        int n = prices.Length;
        for (int i = 0; i < n; i++) {
            profit += prices[i] * strategy[i];
        }
        long maximumProfit = profit;
        int modifyIndex = -1;
        long delta = 0;
        for (int i = 0; i < k; i++) {
            delta -= prices[i] * strategy[i];
            if (i >= k / 2) {
                delta += prices[i];
            }
        }
        if (profit + delta > maximumProfit) {
            maximumProfit = profit + delta;
            modifyIndex = 0;
        }
        for (int i = k; i < n; i++) {
            delta += prices[i - k] * strategy[i - k];
            delta -= prices[i - k / 2];
            delta += prices[i] - prices[i] * strategy[i];
            if (profit + delta > maximumProfit) {
                maximumProfit = profit + delta;
                modifyIndex = i - k + 1;
            }
        }
        return modifyIndex;
    }
}

###C++

class Solution {
public:
    int maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        long long profit = 0;
        int n = prices.size();
        for (int i = 0; i < n; i++) {
            profit += prices[i] * strategy[i];
        }
        long long maximumProfit = profit;
        int modifyIndex = -1;
        long long delta = 0;
        for (int i = 0; i < k; i++) {
            delta -= prices[i] * strategy[i];
            if (i >= k / 2) {
                delta += prices[i];
            }
        }
        if (profit + delta > maximumProfit) {
            maximumProfit = profit + delta;
            modifyIndex = 0;
        }
        for (int i = k; i < n; i++) {
            delta += prices[i - k] * strategy[i - k];
            delta -= prices[i - k / 2];
            delta += prices[i] - prices[i] * strategy[i];
            if (profit + delta > maximumProfit) {
                maximumProfit = profit + delta;
                modifyIndex = i - k + 1;
            }
        }
        return modifyIndex;
    }
};

###Python

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        profit = 0
        n = len(prices)
        for i in range(n):
            profit += prices[i] * strategy[i]
        maximumProfit = profit
        modifyIndex = -1
        delta = 0
        for i in range(k):
            delta -= prices[i] * strategy[i]
            if i >= k // 2:
                delta += prices[i]
        if profit + delta > maximumProfit:
            maximumProfit = profit + delta
            modifyIndex = 0
        for i in range(k, n):
            delta += prices[i - k] * strategy[i - k]
            delta -= prices[i - k // 2]
            delta += prices[i] - prices[i] * strategy[i]
            maximumProfit = max(maximumProfit, profit + delta)
            if profit + delta > maximumProfit:
                maximumProfit = profit + delta
                modifyIndex = i - k + 1
        return modifyIndex

###C

int maxProfit(int* prices, int pricesSize, int* strategy, int strategySize, int k) {
    long long profit = 0;
    for (int i = 0; i < pricesSize; i++) {
        profit += prices[i] * strategy[i];
    }
    long long maximumProfit = profit;
    int modifyIndex = -1;
    long long delta = 0;
    for (int i = 0; i < k; i++) {
        delta -= prices[i] * strategy[i];
        if (i >= k / 2) {
            delta += prices[i];
        }
    }
    if (profit + delta > maximumProfit) {
        maximumProfit = profit + delta;
        modifyIndex = 0;
    }
    for (int i = k; i < pricesSize; i++) {
        delta += prices[i - k] * strategy[i - k];
        delta -= prices[i - k / 2];
        delta += prices[i] - prices[i] * strategy[i];
        if (profit + delta > maximumProfit) {
            maximumProfit = profit + delta;
            modifyIndex = i - k + 1;
        }
    }
    return modifyIndex;
}

###Go

func maxProfit(prices []int, strategy []int, k int) int {
    profit := int64(0)
    n := len(prices)
    for i := 0; i < n; i++ {
        profit += int64(prices[i] * strategy[i])
    }
    maximumProfit := profit
    modifyIndex := -1
    delta := int64(0)
    for i := 0; i < k; i++ {
        delta -= int64(prices[i] * strategy[i])
        if i >= k / 2 {
            delta += int64(prices[i])
        }
    }
    if profit + delta > maximumProfit {
        maximumProfit = profit + delta
        modifyIndex = 0
    }
    for i := k; i < n; i++ {
        delta += int64(prices[i - k] * strategy[i - k])
        delta -= int64(prices[i - k / 2])
        delta += int64(prices[i] - prices[i] * strategy[i])
        if profit + delta > maximumProfit {
            maximumProfit = profit + delta
            modifyIndex = i - k + 1
        }
    }
    return modifyIndex
}

###JavaScript

var maxProfit = function(prices, strategy, k) {
    let profit = 0;
    let n = prices.length;
    for (let i = 0; i < n; i++) {
        profit += prices[i] * strategy[i];
    }
    let maximumProfit = profit;
    let modifyIndex = -1;
    let delta = 0;
    for (let i = 0; i < k; i++) {
        delta -= prices[i] * strategy[i];
        if (i >= k / 2) {
            delta += prices[i];
        }
    }
    if (profit + delta > maximumProfit) {
        maximumProfit = profit + delta;
        modifyIndex = 0;
    }
    for (let i = k; i < n; i++) {
        delta += prices[i - k] * strategy[i - k];
        delta -= prices[i - k / 2];
        delta += prices[i] - prices[i] * strategy[i];
        if (profit + delta > maximumProfit) {
            maximumProfit = profit + delta;
            modifyIndex = i - k + 1;
        }
    }
    return modifyIndex;
};

###TypeScript

function maxProfit(prices: number[], strategy: number[], k: number): number {
    let profit = 0;
    let n = prices.length;
    for (let i = 0; i < n; i++) {
        profit += prices[i] * strategy[i];
    }
    let maximumProfit = profit;
    let modifyIndex = -1;
    let delta = 0;
    for (let i = 0; i < k; i++) {
        delta -= prices[i] * strategy[i];
        if (i >= k / 2) {
            delta += prices[i];
        }
    }
    if (profit + delta > maximumProfit) {
        maximumProfit = profit + delta;
        modifyIndex = 0;
    }
    for (let i = k; i < n; i++) {
        delta += prices[i - k] * strategy[i - k];
        delta -= prices[i - k / 2];
        delta += prices[i] - prices[i] * strategy[i];
        if (profit + delta > maximumProfit) {
            maximumProfit = profit + delta;
            modifyIndex = i - k + 1;
        }
    }
    return modifyIndex;
};

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{prices}$ 和 $\textit{strategy}$ 的长度。由于遍历过程和原始问题解法相同，因此和原始问题解法的时间复杂度相同。

• 空间复杂度：$O(n)$ 或 $O(1)$，其中 $n$ 是数组 $\textit{prices}$ 和 $\textit{strategy}$ 的长度。解法一对应的实现空间复杂度是 $O(n)$，解法二对应的实现空间复杂度是 $O(1)$。

方法一：前缀和

计算两个前缀和数组：

• 定义数组 $c$，其中 $c[i] = \textit{prices}[i]\cdot \textit{strategy}[i]$。计算 $c$ 的前缀和，记作 $\textit{sum}$。
• 计算 $\textit{prices}$ 的前缀和，记作 $\textit{sumSell}$。
• 关于前缀和数组的详细定义，请看 前缀和。

如果不修改，答案为 $\textit{sum}[n]$。

如果修改，枚举修改子数组 $[i-k,i-1]$。修改后的利润由三部分组成：

1. $[0,i-k-1]$ 的 $\textit{prices}[i]\cdot \textit{strategy}[i]$ 之和，即 $\textit{sum}[i-k]$。
2. $[i,n-1]$ 的 $\textit{prices}[i]\cdot \textit{strategy}[i]$ 之和，即 $\textit{sum}[n] - \textit{sum}[i]$。
3. $[i-k/2,i-1]$ 的 $\textit{prices}[i]$ 之和，即 $\textit{sumSell}[i] - \textit{sumSell}[i-k/2]$。

总和为

$$
\textit{sum}[i-k] + \textit{sum}[n] - \textit{sum}[i] + \textit{sumSell}[i] - \textit{sumSell}[i-k/2]
$$

用上式更新答案的最大值。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        n = len(prices)
        s = list(accumulate((p * s for p, s in zip(prices, strategy)), initial=0))
        s_sell = list(accumulate(prices, initial=0))

        # 修改一次
        ans = max(s[i - k] + s[n] - s[i] + s_sell[i] - s_sell[i - k // 2] for i in range(k, n + 1))
        return max(ans, s[n])  # 不修改

###java

class Solution {
    public long maxProfit(int[] prices, int[] strategy, int k) {
        int n = prices.length;
        long[] sum = new long[n + 1];
        long[] sumSell = new long[n + 1];
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + prices[i] * strategy[i];
            sumSell[i + 1] = sumSell[i] + prices[i];
        }

        long ans = sum[n]; // 不修改
        for (int i = k; i <= n; i++) {
            long res = sum[i - k] + sum[n] - sum[i] + sumSell[i] - sumSell[i - k / 2];
            ans = Math.max(ans, res);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        int n = prices.size();
        vector<long long> sum(n + 1), sum_sell(n + 1);
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + prices[i] * strategy[i];
            sum_sell[i + 1] = sum_sell[i] + prices[i];
        }

        long long ans = sum[n]; // 不修改
        for (int i = k; i <= n; i++) {
            long long res = sum[i - k] + sum[n] - sum[i] + sum_sell[i] - sum_sell[i - k / 2];
            ans = max(ans, res);
        }
        return ans;
    }
};

###go

func maxProfit(prices []int, strategy []int, k int) int64 {
n := len(prices)
sum := make([]int, n+1)
sumSell := make([]int, n+1)
for i, p := range prices {
sum[i+1] = sum[i] + p*strategy[i]
sumSell[i+1] = sumSell[i] + p
}

ans := sum[n] // 不修改
for i := k; i <= n; i++ {
res := sum[i-k] + sum[n] - sum[i] + sumSell[i] - sumSell[i-k/2]
ans = max(ans, res)
}
return int64(ans)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{prices}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

方法二：定长滑动窗口

前置知识：定长滑动窗口。

设不修改时的利润为 $\textit{total}$。修改后，利润（相比不修改）增加了 $\textit{sum}$。所有窗口的 $\textit{sum}$ 的最大值为 $\textit{maxSum}$。那么答案为 $\textit{total} + \max(\textit{maxSum},0)$。这里可能出现 $\textit{maxSum} < 0$ 的情况，此时不修改更好，也就是与 $0$ 取最大值。

对于价格 $\textit{p}$，如果修改前策略是 $x$，修改后策略是 $y$，那么利润增加了 $p\cdot(y-x)$。比如原来买入，现在持有（不买入），那么利润增加了 $p\cdot (0 - (-1)) = p$。又比如原来买入，现在卖出，那么利润增加了 $p\cdot (1 - (-1)) = 2p$。

下面来计算每个窗口的 $\textit{sum}$。考察从 $[i-k,i-1]$ 向右滑到 $[i-k+1,i]$，$\textit{sum}$ 如何变化。

先看窗口 $[i-k,i-1]$ 的 $\textit{sum}$，分为左右两部分：

1. 左半为 $[i-k,i-k/2-1]$。修改前的策略为 $\textit{strategy}[j]$，修改后的策略为 $0$，所以利润增加了 $\textit{prices}[j]\cdot (-\textit{strategy}[j])$ 之和，其中 $j$ 在左半中。
2. 右半为 $[i-k/2,i-1]$。修改前的策略为 $\textit{strategy}[j]$，修改后的策略为 $1$，所以利润增加了 $\textit{prices}[j]\cdot (1-\textit{strategy}[j])$ 之和，其中 $j$ 在右半中。

当窗口向右滑动时，有三个位置的元素发生了变化：

1. $i$ 进入窗口（在右半），$\textit{sum}$ 增加了 $\textit{prices}[i]\cdot (1-\textit{strategy}[i])$。
2. 下标为 $i-k/2$ 的元素从右半移到左半，交易策略从 $1$ 变成 $0$，所以 $\textit{sum}$ 减少了 $\textit{prices}[i-k/2]$。
3. $i-k$ 离开窗口（离开前在左半），$\textit{sum}$ 减少了 $\textit{prices}[i-k]\cdot (-\textit{strategy}[i-k])$。

写法一

###py

# 手写 max 更快
max = lambda a, b: b if b > a else a

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        total = s = 0
        # 计算第一个窗口的 s
        for p, st in zip(prices[:k // 2], strategy[:k // 2]):
            total += p * st
            s -= p * st
        for p, st in zip(prices[k // 2: k], strategy[k // 2: k]):
            total += p * st
            s += p * (1 - st)

        max_s = max(s, 0)
        # 向右滑动，计算后续窗口的 s
        for i in range(k, len(prices)):
            p, st = prices[i], strategy[i]
            total += p * st
            s += p * (1 - st) - prices[i - k // 2] + prices[i - k] * strategy[i - k]
            max_s = max(max_s, s)
        return total + max_s

###java

class Solution {
    public long maxProfit(int[] prices, int[] strategy, int k) {
        long total = 0, sum = 0;
        // 计算第一个窗口的 sum
        for (int i = 0; i < k / 2; i++) {
            int p = prices[i], s = strategy[i];
            total += p * s;
            sum -= p * s;
        }
        for (int i = k / 2; i < k; i++) {
            int p = prices[i], s = strategy[i];
            total += p * s;
            sum += p * (1 - s);
        }

        long maxSum = Math.max(sum, 0);
        // 向右滑动，计算后续窗口的 sum
        for (int i = k; i < prices.length; i++) {
            int p = prices[i], s = strategy[i];
            total += p * s;
            sum += p * (1 - s) - prices[i - k / 2] + prices[i - k] * strategy[i - k];
            maxSum = Math.max(maxSum, sum);
        }
        return total + maxSum;
    }
}

###cpp

class Solution {
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        long long total = 0, sum = 0;
        // 计算第一个窗口的 sum
        for (int i = 0; i < k / 2; i++) {
            int p = prices[i], s = strategy[i];
            total += p * s;
            sum -= p * s;
        }
        for (int i = k / 2; i < k; i++) {
            int p = prices[i], s = strategy[i];
            total += p * s;
            sum += p * (1 - s);
        }

        long long max_sum = max(sum, 0LL);
        // 向右滑动，计算后续窗口的 sum
        for (int i = k; i < prices.size(); i++) {
            int p = prices[i], s = strategy[i];
            total += p * s;
            sum += p * (1 - s) - prices[i - k / 2] + prices[i - k] * strategy[i - k];
            max_sum = max(max_sum, sum);
        }
        return total + max_sum;
    }
};

###go

func maxProfit(prices, strategy []int, k int) int64 {
total, sum := 0, 0
// 计算第一个窗口的 sum
for i := range k / 2 {
p, s := prices[i], strategy[i]
total += p * s
sum -= p * s
}
for i := k / 2; i < k; i++ {
p, s := prices[i], strategy[i]
total += p * s
sum += p * (1 - s)
}

maxSum := max(sum, 0)
// 向右滑动，计算后续窗口的 sum
for i := k; i < len(prices); i++ {
p, s := prices[i], strategy[i]
total += p * s
sum += p*(1-s) - prices[i-k/2] + prices[i-k]*strategy[i-k]
maxSum = max(maxSum, sum)
}
return int64(total + maxSum)
}

写法二

###py

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        total = max_s = s = 0
        for i, (p, st) in enumerate(zip(prices, strategy)):
            total += p * st

            # 1. 入右半，交易策略从 st 变成 1
            s += p * (1 - st)

            if i < k - 1:  # 尚未形成第一个窗口
                # 在下一轮循环中，下标为 i-k/2+1 的元素从右半移到左半，交易策略从 1 变成 0
                if i >= k // 2 - 1:  
                    s -= prices[i - k // 2 + 1]
                continue

            # 2. 更新
            max_s = max(max_s, s)

            # 3. 出，为下一个窗口做准备
            # 对于下一个窗口，下标为 i-k/2+1 的元素从右半移到左半，交易策略从 1 变成 0，下标为 i-k+1 的元素从左半离开窗口
            s -= prices[i - k // 2 + 1] - prices[i - k + 1] * strategy[i - k + 1]

        return total + max_s

###java

class Solution {
    public long maxProfit(int[] prices, int[] strategy, int k) {
        long total = 0, maxSum = 0, sum = 0;
        for (int i = 0; i < prices.length; i++) {
            int p = prices[i], s = strategy[i];
            total += p * s;

            // 1. 入右半，交易策略从 s 变成 1
            sum += p * (1 - s);

            if (i < k - 1) { // 尚未形成第一个窗口
                // 在下一轮循环中，下标为 i-k/2+1 的元素从右半移到左半，交易策略从 1 变成 0
                if (i >= k / 2 - 1) {
                    sum -= prices[i - k / 2 + 1];
                }
                continue;
            }

            // 2. 更新
            maxSum = Math.max(maxSum, sum);

            // 3. 出，为下一个窗口做准备
            // 对于下一个窗口，下标为 i-k/2+1 的元素从右半移到左半，交易策略从 1 变成 0，下标为 i-k+1 的元素从左半离开窗口
            sum -= prices[i - k / 2 + 1] - prices[i - k + 1] * strategy[i - k + 1];
        }

        return total + maxSum;
    }
}

###cpp

class Solution {
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        long long total = 0, max_sum = 0, sum = 0;
        for (int i = 0; i < prices.size(); i++) {
            int p = prices[i], s = strategy[i];
            total += p * s;

            // 1. 入右半，交易策略从 s 变成 1
            sum += p * (1 - s);

            if (i < k - 1) { // 尚未形成第一个窗口
                // 在下一轮循环中，下标为 i-k/2+1 的元素从右半移到左半，交易策略从 1 变成 0
                if (i >= k / 2 - 1) {
                    sum -= prices[i - k / 2 + 1];
                }
                continue;
            }

            // 2. 更新
            max_sum = max(max_sum, sum);

            // 3. 出，为下一个窗口做准备
            // 对于下一个窗口，下标为 i-k/2+1 的元素从右半移到左半，交易策略从 1 变成 0，下标为 i-k+1 的元素从左半离开窗口
            sum -= prices[i - k / 2 + 1] - prices[i - k + 1] * strategy[i - k + 1];
        }

        return total + max_sum;
    }
};

###go

func maxProfit(prices, strategy []int, k int) int64 {
var total, maxSum, sum int
for i, p := range prices {
s := strategy[i]
total += p * s

// 1. 入右半，交易策略从 s 变成 1
sum += p * (1 - s)

if i < k-1 { // 尚未形成第一个窗口
// 在下一轮循环中，下标为 i-k/2+1 的元素从右半移到左半，交易策略从 1 变成 0
if i >= k/2-1 {
sum -= prices[i-k/2+1]
}
continue
}

// 2. 更新
maxSum = max(maxSum, sum)

// 3. 出，为下一个窗口做准备
// 对于下一个窗口，下标为 i-k/2+1 的元素从右半移到左半，交易策略从 1 变成 0，下标为 i-k+1 的元素从左半离开窗口
sum -= prices[i-k/2+1] - prices[i-k+1]*strategy[i-k+1]
}

return int64(total + maxSum)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{prices}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

专题训练

1. 数据结构题单的「一、前缀和」。
2. 滑动窗口题单的「一、定长滑动窗口」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：动态规划

我们定义 $f[i][j][k]$ 表示在前 $i$ 天内，最多进行 $j$ 笔交易，且当前状态为 $k$ 时的最大利润。这里的状态 $k$ 有三种可能：

• 若 $k = 0$，表示当前没有持有股票。
• 若 $k = 1$，表示当前持有一支股票。
• 若 $k = 2$，表示当前持有一支股票的空头。

初始时，对任意 $j \in [1, k]$，都有 $f[0][j][1] = -prices[0]$ 和 $f[0][j][2] = prices[0]$。这表示在第 0 天买入一支股票或卖出一支股票的空头。

接下来，我们可以通过状态转移来更新 $f[i][j][k]$ 的值。对于每一天 $i$ 和每笔交易 $j$，我们可以根据当前状态 $k$ 来决定如何更新：

• 若 $k = 0$，表示当前没有持有股票，这个状态可以由以下三种情况转移而来：
  • 前一天没有持有股票。
  • 前一天持有一支股票，并在今天卖出。
  • 前一天持有一支股票的空头，并在今天买回。
• 若 $k = 1$，表示当前持有一支股票，这个状态可以由以下两种情况转移而来：
  • 前一天持有一支股票。
  • 前一天没有持有股票，并在今天买入。
• 若 $k = 2$，表示当前持有一支股票的空头，这个状态可以由以下两种情况转移而来：
  • 前一天持有一支股票的空头。
  • 前一天没有持有股票，并在今天卖出。

即，对于 $1 \leq i < n$ 和 $1 \leq j \leq k$，我们有以下状态转移方程：

$$
\begin{aligned}
f[i][j][0] &= \max(f[i - 1][j][0], f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]) \
f[i][j][1] &= \max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]) \
f[i][j][2] &= \max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i])
\end{aligned}
$$

最终，我们需要返回 $f[n - 1][k][0]$，即在前 $n$ 天内，最多进行 $k$ 笔交易，且当前没有持有股票时的最大利润。

###python

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        n = len(prices)
        f = [[[0] * 3 for _ in range(k + 1)] for _ in range(n)]
        for j in range(1, k + 1):
            f[0][j][1] = -prices[0]
            f[0][j][2] = prices[0]
        for i in range(1, n):
            for j in range(1, k + 1):
                f[i][j][0] = max(
                    f[i - 1][j][0],
                    f[i - 1][j][1] + prices[i],
                    f[i - 1][j][2] - prices[i],
                )
                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i])
                f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i])
        return f[n - 1][k][0]

###java

class Solution {
    public long maximumProfit(int[] prices, int k) {
        int n = prices.length;
        long[][][] f = new long[n][k + 1][3];
        for (int j = 1; j <= k; ++j) {
            f[0][j][1] = -prices[0];
            f[0][j][2] = prices[0];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j][0] = Math.max(f[i - 1][j][0],
                    Math.max(f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]));
                f[i][j][1] = Math.max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
                f[i][j][2] = Math.max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]);
            }
        }
        return f[n - 1][k][0];
    }
}

###cpp

class Solution {
public:
    long long maximumProfit(vector<int>& prices, int k) {
        int n = prices.size();
        long long f[n][k + 1][3];
        memset(f, 0, sizeof(f));
        for (int j = 1; j <= k; ++j) {
            f[0][j][1] = -prices[0];
            f[0][j][2] = prices[0];
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j][0] = max({f[i - 1][j][0], f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]});
                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
                f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]);
            }
        }

        return f[n - 1][k][0];
    }
};

###go

func maximumProfit(prices []int, k int) int64 {
n := len(prices)
f := make([][][3]int, n)
for i := range f {
f[i] = make([][3]int, k+1)
}

for j := 1; j <= k; j++ {
f[0][j][1] = -prices[0]
f[0][j][2] = prices[0]
}

for i := 1; i < n; i++ {
for j := 1; j <= k; j++ {
f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1]+prices[i], f[i-1][j][2]-prices[i])
f[i][j][1] = max(f[i-1][j][1], f[i-1][j-1][0]-prices[i])
f[i][j][2] = max(f[i-1][j][2], f[i-1][j-1][0]+prices[i])
}
}

return int64(f[n-1][k][0])
}

###ts

function maximumProfit(prices: number[], k: number): number {
    const n = prices.length;
    const f: number[][][] = Array.from({ length: n }, () =>
        Array.from({ length: k + 1 }, () => Array(3).fill(0)),
    );

    for (let j = 1; j <= k; ++j) {
        f[0][j][1] = -prices[0];
        f[0][j][2] = prices[0];
    }

    for (let i = 1; i < n; ++i) {
        for (let j = 1; j <= k; ++j) {
            f[i][j][0] = Math.max(
                f[i - 1][j][0],
                f[i - 1][j][1] + prices[i],
                f[i - 1][j][2] - prices[i],
            );
            f[i][j][1] = Math.max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
            f[i][j][2] = Math.max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]);
        }
    }

    return f[n - 1][k][0];
}

###rust

impl Solution {
    pub fn maximum_profit(prices: Vec<i32>, k: i32) -> i64 {
        let n = prices.len();
        let k = k as usize;
        let mut f = vec![vec![vec![0i64; 3]; k + 1]; n];
        for j in 1..=k {
            f[0][j][1] = -(prices[0] as i64);
            f[0][j][2] = prices[0] as i64;
        }
        for i in 1..n {
            for j in 1..=k {
                f[i][j][0] = f[i - 1][j][0]
                    .max(f[i - 1][j][1] + prices[i] as i64)
                    .max(f[i - 1][j][2] - prices[i] as i64);
                f[i][j][1] = f[i - 1][j][1].max(f[i - 1][j - 1][0] - prices[i] as i64);
                f[i][j][2] = f[i - 1][j][2].max(f[i - 1][j - 1][0] + prices[i] as i64);
            }
        }
        f[n - 1][k][0]
    }
}

时间复杂度 $O(n \times k)$，空间复杂度 $O(n \times k)$。其中 $n$ 为数组 $\textit{prices}$ 的长度，而 $k$ 为最大交易次数。

---

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~

给你一个整数数组 prices，其中 prices[i] 是第 i 天股票的价格（美元），以及一个整数 k。

你最多可以进行 k 笔交易，每笔交易可以是以下任一类型：

• 普通交易：在第 i 天买入，然后在之后的第 j 天卖出，其中 i < j。你的利润是 prices[j] - prices[i]。

• 做空交易：在第 i 天卖出，然后在之后的第 j 天买回，其中 i < j。你的利润是 prices[i] - prices[j]。

注意：你必须在开始下一笔交易之前完成当前交易。此外，你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。

通过进行 最多 k 笔交易，返回你可以获得的最大总利润。

 

示例 1:

示例 2:

 

提示:

• 2 <= prices.length <= 103
• 1 <= prices[i] <= 109
• 1 <= k <= prices.length / 2

如果只有普通交易，那么本题就是 188. 买卖股票的最佳时机 IV。

回顾一下，188 题中的状态定义为：

• $\textit{dfs}(i,j,0)$ 表示在 $\textit{prices}[0]$ 到 $\textit{prices}[i]$ 中完成至多 $j$ 笔交易，第 $i$ 天结束时未持有股票的最大利润。
• $\textit{dfs}(i,j,1)$ 表示在 $\textit{prices}[0]$ 到 $\textit{prices}[i]$ 中完成至多 $j$ 笔交易，第 $i$ 天结束时持有股票的最大利润。

本题可以做空交易，也就是可以先加再减（普通交易是先减再加）。我们需要额外增加一类状态：

• $\textit{dfs}(i,j,2)$ 表示在 $\textit{prices}[0]$ 到 $\textit{prices}[i]$ 中完成至多 $j$ 笔交易，第 $i$ 天结束时处于做空中（空头状态）的最大利润。

同样地，转移方程增加一条：

$$
\textit{dfs}(i,j,2) = \max(\textit{dfs}(i-1, j, 2), \textit{dfs}(i-1, j-1, 0)+\textit{prices}[i])
$$

分别对应继续处于做空中，或者在第 $i$ 天卖出股票，开始做空（开空）。

此外，对于 $\textit{dfs}(i,j,0)$，在计算最大值时额外考虑在第 $i$ 天买回股票（平空）的情况，即 $\textit{dfs}(i,j,2) - \textit{prices}[i]$。

注意本题可能算出负数，$\textit{memo}$ 数组可以初始化成 $\infty$ 或者 $-\infty$。

什么是做空？简单科普一下~

一、记忆化搜索

###py

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        # 在 [0,i] 中完成至多 j 笔交易，第 i 天【结束时】的状态为 end_state 的情况下的最大收益
        # 0=未持有股票，1=持有股票，2=做空中
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int, end_state: int) -> int:
            if j < 0:
                return -inf
            if i < 0:
                return -inf if end_state else 0
            p = prices[i]
            if end_state == 0:
                return max(dfs(i - 1, j, 0), dfs(i - 1, j, 1) + p, dfs(i - 1, j, 2) - p)
            if end_state == 1:
                return max(dfs(i - 1, j, 1), dfs(i - 1, j - 1, 0) - p)
            return max(dfs(i - 1, j, 2), dfs(i - 1, j - 1, 0) + p)

        ans = dfs(len(prices) - 1, k, 0)
        dfs.cache_clear()  # 防止爆内存（一般来说，状态数达到 1e6 就需要写这个）
        return ans

###java

class Solution {
    private int[] prices;
    private long[][][] memo;

    public long maximumProfit(int[] prices, int k) {
        this.prices = prices;
        int n = prices.length;
        memo = new long[n][k + 1][3];
        for (long[][] mat : memo) {
            for (long[] row : mat) {
                Arrays.fill(row, Long.MIN_VALUE); // MIN_VALUE 表示还没有计算过
            }
        }
        return dfs(n - 1, k, 0);
    }

    // 在 [0,i] 中完成至多 j 笔交易，第 i 天【结束时】的状态为 endState 的情况下的最大收益
    // 0=未持有股票，1=持有股票，2=做空中
    private long dfs(int i, int j, int endState) {
        if (j < 0) {
            return Long.MIN_VALUE / 2; // 除 2 防止溢出
        }
        if (i < 0) {
            return endState > 0 ? Long.MIN_VALUE / 2 : 0;
        }
        if (memo[i][j][endState] != Long.MIN_VALUE) { // 之前计算过
            return memo[i][j][endState];
        }
        int p = prices[i];
        if (endState == 0) {
            return memo[i][j][endState] = Math.max(dfs(i - 1, j, 0), Math.max(dfs(i - 1, j, 1) + p, dfs(i - 1, j, 2) - p));
        }
        if (endState == 1) {
            return memo[i][j][endState] = Math.max(dfs(i - 1, j, 1), dfs(i - 1, j - 1, 0) - p);
        }
        return memo[i][j][endState] = Math.max(dfs(i - 1, j, 2), dfs(i - 1, j - 1, 0) + p);
    }
}

###cpp

class Solution {
public:
    long long maximumProfit(vector<int>& prices, int k) {
        int n = prices.size();
        vector memo(n, vector<array<long long, 3>>(k + 1, {LLONG_MIN, LLONG_MIN, LLONG_MIN})); // LLONG_MIN 表示还没有计算过

        // 在 [0,i] 中完成至多 j 笔交易，第 i 天【结束时】的状态为 end_state 的情况下的最大收益
        // 0=未持有股票，1=持有股票，2=做空中
        auto dfs = [&](this auto&& dfs, int i, int j, int end_state) -> long long {
            if (j < 0) {
                return LLONG_MIN / 2; // 除 2 防止溢出
            }
            if (i < 0) {
                return end_state ? LLONG_MIN / 2 : 0;
            }
            long long& res = memo[i][j][end_state]; // 注意这里是引用
            if (res != LLONG_MIN) { // 之前计算过
                return res;
            }
            int p = prices[i];
            if (end_state == 0) {
                return res = max({dfs(i - 1, j, 0), dfs(i - 1, j, 1) + p, dfs(i - 1, j, 2) - p});
            }
            if (end_state == 1) {
                return res = max(dfs(i - 1, j, 1), dfs(i - 1, j - 1, 0) - p);
            }
            return res = max(dfs(i - 1, j, 2), dfs(i - 1, j - 1, 0) + p);
        };

        return dfs(n - 1, k, 0);
    }
};

###go

func maximumProfit(prices []int, k int) int64 {
n := len(prices)
memo := make([][][3]int, n)
for i := range memo {
memo[i] = make([][3]int, k+1)
for j := range memo[i] {
memo[i][j] = [3]int{math.MinInt, math.MinInt, math.MinInt} // MinInt 表示还没有计算过
}
}

// 在 [0,i] 中完成至多 j 笔交易，第 i 天【结束时】的状态为 endState 的情况下的最大收益
// 0=未持有股票，1=持有股票，2=做空中
var dfs func(int, int, int) int
dfs = func(i, j, endState int) (res int) {
if j < 0 {
return math.MinInt / 2 // 防止溢出
}
if i < 0 {
if endState == 1 {
return math.MinInt / 2
}
return
}
ptr := &memo[i][j][endState]
if *ptr != math.MinInt { // 之前计算过
return *ptr
}
defer func() { *ptr = res }() // 记忆化
p := prices[i]
if endState == 0 {
return max(dfs(i-1, j, 0), dfs(i-1, j, 1)+p, dfs(i-1, j, 2)-p)
}
if endState == 1 {
return max(dfs(i-1, j, 1), dfs(i-1, j-1, 0)-p)
}
return max(dfs(i-1, j, 2), dfs(i-1, j-1, 0)+p)
}

return int64(dfs(n-1, k, 0))
}

二、1:1 翻译成递推

###py

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        n = len(prices)
        f = [[[-inf] * 3 for _ in range(k + 2)] for _ in range(n + 1)]
        for j in range(1, k + 2):
            f[0][j][0] = 0
        for i, p in enumerate(prices):
            for j in range(1, k + 2):
                f[i + 1][j][0] = max(f[i][j][0], f[i][j][1] + p, f[i][j][2] - p)
                f[i + 1][j][1] = max(f[i][j][1], f[i][j - 1][0] - p)
                f[i + 1][j][2] = max(f[i][j][2], f[i][j - 1][0] + p)
        return f[-1][-1][0]

###java

class Solution {
    public long maximumProfit(int[] prices, int k) {
        int n = prices.length;
        long[][][] f = new long[n + 1][k + 2][3];
        for (long[][] mat : f) {
            for (long[] row : mat) {
                Arrays.fill(row, Long.MIN_VALUE / 2);
            }
        }
        for (int j = 1; j <= k + 1; j++) {
            f[0][j][0] = 0;
        }
        for (int i = 0; i < n; i++) {
            int p = prices[i];
            for (int j = 1; j <= k + 1; j++) {
                f[i + 1][j][0] = Math.max(f[i][j][0], Math.max(f[i][j][1] + p, f[i][j][2] - p));
                f[i + 1][j][1] = Math.max(f[i][j][1], f[i][j - 1][0] - p);
                f[i + 1][j][2] = Math.max(f[i][j][2], f[i][j - 1][0] + p);
            }
        }
        return f[n][k + 1][0];
    }
}

###cpp

class Solution {
public:
    long long maximumProfit(vector<int>& prices, int k) {
        int n = prices.size();
        vector f(n + 1, vector<array<long long, 3>>(k + 2, {LLONG_MIN / 2, LLONG_MIN / 2, LLONG_MIN / 2}));
        for (int j = 1; j <= k + 1; j++) {
            f[0][j][0] = 0;
        }
        for (int i = 0; i < n; i++) {
            int p = prices[i];
            for (int j = 1; j <= k + 1; j++) {
                f[i + 1][j][0] = max({f[i][j][0], f[i][j][1] + p, f[i][j][2] - p});
                f[i + 1][j][1] = max(f[i][j][1], f[i][j - 1][0] - p);
                f[i + 1][j][2] = max(f[i][j][2], f[i][j - 1][0] + p);
            }
        }
        return f[n][k + 1][0];
    }
};

###go

func maximumProfit(prices []int, k int) int64 {
n := len(prices)
f := make([][][3]int, n+1)
for i := range f {
f[i] = make([][3]int, k+2)
for j := range f[i] {
f[i][j] = [3]int{math.MinInt / 2, math.MinInt / 2, math.MinInt / 2}
}
}
for j := 1; j <= k+1; j++ {
f[0][j][0] = 0
}
for i, p := range prices {
for j := 1; j <= k+1; j++ {
f[i+1][j][0] = max(f[i][j][0], f[i][j][1]+p, f[i][j][2]-p)
f[i+1][j][1] = max(f[i][j][1], f[i][j-1][0]-p)
f[i+1][j][2] = max(f[i][j][2], f[i][j-1][0]+p)
}
}
return int64(f[n][k+1][0])
}

三、空间优化

###py

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        f = [[-inf] * 3 for _ in range(k + 2)]
        for j in range(1, k + 2):
            f[j][0] = 0
        for p in prices:
            for j in range(k + 1, 0, -1):
                f[j][0] = max(f[j][0], f[j][1] + p, f[j][2] - p)
                f[j][1] = max(f[j][1], f[j - 1][0] - p)
                f[j][2] = max(f[j][2], f[j - 1][0] + p)
        return f[-1][0]

###java

class Solution {
    public long maximumProfit(int[] prices, int k) {
        long[][] f = new long[k + 2][3];
        for (int j = 1; j <= k + 1; j++) {
            f[j][1] = Long.MIN_VALUE / 2; // 防止溢出
        }
        f[0][0] = Long.MIN_VALUE / 2;
        for (int p : prices) {
            for (int j = k + 1; j > 0; j--) {
                f[j][0] = Math.max(f[j][0], Math.max(f[j][1] + p, f[j][2] - p));
                f[j][1] = Math.max(f[j][1], f[j - 1][0] - p);
                f[j][2] = Math.max(f[j][2], f[j - 1][0] + p);
            }
        }
        return f[k + 1][0];
    }
}

###cpp

class Solution {
public:
    long long maximumProfit(vector<int>& prices, int k) {
        vector<array<long long, 3>> f(k + 2, {LLONG_MIN / 2, LLONG_MIN / 2, LLONG_MIN / 2});
        for (int j = 1; j <= k + 1; j++) {
            f[j][0] = 0;
        }
        for (int p : prices) {
            for (int j = k + 1; j > 0; j--) {
                // f[j][0] = max({f[j][0], f[j][1] + p, f[j][2] - p}); 这种写法比下面的慢
                f[j][0] = max(f[j][0], max(f[j][1] + p, f[j][2] - p));
                f[j][1] = max(f[j][1], f[j - 1][0] - p);
                f[j][2] = max(f[j][2], f[j - 1][0] + p);
            }
        }
        return f[k + 1][0];
    }
};

###go

func maximumProfit(prices []int, k int) int64 {
f := make([][3]int, k+2)
for j := 1; j <= k+1; j++ {
f[j][1] = math.MinInt / 2
f[j][2] = math.MinInt / 2
}
f[0][0] = math.MinInt / 2
for _, p := range prices {
for j := k + 1; j > 0; j-- {
f[j][0] = max(f[j][0], f[j][1]+p, f[j][2]-p)
f[j][1] = max(f[j][1], f[j-1][0]-p)
f[j][2] = max(f[j][2], f[j-1][0]+p)
}
}
return int64(f[k+1][0])
}

复杂度分析

• 时间复杂度：$\mathcal{O}(nk)$，其中 $n$ 是 $\textit{prices}$ 的长度。
• 空间复杂度：$\mathcal{O}(k)$。

专题训练

见下面动态规划题单的「六、状态机 DP」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

解法：DP

和这类题之前的题目类似，维护 $f(i, j, t)$ 表示第 $i$ 天结束时，已经开启了 $j$ 次交易，且当前交易状态为 $t$ 的最大利润。$t = 0$ 表示当前不在交易中，$t = 1$ 表示正在进行普通交易（已经完成买入，还未卖出），$t = 2$ 表示正在进行做空交易（已经完成卖出，还未买入）。转移方程有以下几种情况：

1. 第 $i$ 天不操作，则 $f(i, j, t) \xleftarrow{\min} f(i - 1, j, t)$。
2. 第 $i$ 天开始一次普通交易，则 $f(i, j, 1) \xleftarrow{\min} f(i - 1, j - 1, 0) - p_i$。
3. 第 $i$ 天开始一次做空交易，则 $f(i, j, 2) \xleftarrow{\min} f(i - 1, j - 1, 0) + p_i$。
4. 第 $i$ 天结束一次普通交易，则 $f(i, j, 0) \xleftarrow{\min} f(i - 1, j, 1) + p_i$。
5. 第 $i$ 天结束一次做空交易，则 $f(i, j, 0) \xleftarrow{\min} f(i - 1, j, 2) - p_i$。

复杂度 $\mathcal{O}(nk)$。

参考代码（c++）

class Solution {
public:
    long long maximumProfit(vector<int>& prices, int K) {
        int n = prices.size();

        const long long INF = 1e18;
        long long f[n + 1][K + 1][3];
        for (int i = 0; i <= n; i++) for (int k = 0; k <= K; k++) for (int t = 0; t < 3; t++) f[i][k][t] = -INF;
        f[0][0][0] = 0;

        for (int i = 1; i <= n; i++) for (int k = 0; k <= K; k++) {
            // 不交易
            for (int t = 0; t < 3; t++) f[i][k][t] = max(f[i][k][t], f[i - 1][k][t]);
            if (k > 0) {
                // 开始普通交易
                f[i][k][1] = max(f[i][k][1], f[i - 1][k - 1][0] - prices[i - 1]);
                // 开始做空交易
                f[i][k][2] = max(f[i][k][2], f[i - 1][k - 1][0] + prices[i - 1]);
            }
            // 结束普通交易
            f[i][k][0] = max(f[i][k][0], f[i - 1][k][1] + prices[i - 1]);
            // 结束做空交易
            f[i][k][0] = max(f[i][k][0], f[i - 1][k][2] - prices[i - 1]);
        }

        long long ans = -INF;
        for (int k = 0; k <= K; k++) ans = max(ans, f[n][k][0]);
        return ans;
    }
};