解法一
思路和算法
用 $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;
};
复杂度分析
拓展问题
问题描述
原始问题只有计算最大利润，在原始问题的基础上，可以提出拓展问题：当利润最大时，是否应修改策略，如果修改策略则应如何修改策略？如果有多种方案，返回其中任意一种。
解法分析
原始问题的两种解法都是首先计算不修改策略的利润，然后分别计算每个长度为 $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)$。
登录
