题目描述
给你一个整数数组 arr
和一个整数 k
。
首先,我们要对该数组进行修改,即把原数组 arr
重复 k
次。
举个例子,如果 arr = [1, 2]
且 k = 3
,那么修改后的数组就是 [1, 2, 1, 2, 1, 2]
。
然后,请你返回修改后的数组中的最大的子数组之和。
注意,子数组长度可以是 0
,在这种情况下它的总和也是 0
。
由于 结果可能会很大,所以需要 模(mod)10^9 + 7
后再返回。
样例
输入:arr = [1,2], k = 3
输出:9
输入:arr = [1,-2,1], k = 5
输出:2
输入:arr = [-1,-2], k = 7
输出:0
限制
1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4
算法
(前缀和,贪心) $O(n)$
- 我们考虑答案都有哪些可能:
- 答案为
0
。 - 答案仅从当前不串联的数组中得到。
- 答案从
k = 2
的串联结果得到,第一部分的后缀和的最大值加上第二部分的前缀和的最大值。 - 答案从整个串联
k > 2
次后的结果得到,且一定是第一部分的后缀和的最大值,中间部分的总和,加上最后一部分的前缀和的最大值。
- 答案为
- 第二种可能可以从当前前缀和减去当前前缀和的最小值得到。前缀和的最大值直接可以维护出来,后缀和的最大值可以通过总和减去前缀和的最小值得到。
时间复杂度
- 仅遍历数组一次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要额外空间存储前缀和,前缀和的最小值和前缀和的最大值。故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
int kConcatenationMaxSum(vector<int>& arr, int k) {
#define LL long long
const int mod = 1000000007;
int n = arr.size();
vector<LL> sum(n + 1, 0);
vector<LL> minr(n + 1, 0);
vector<LL> maxr(n + 1, 0);
LL ans = 0;
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + arr[i - 1];
minr[i] = min(minr[i - 1], sum[i]);
maxr[i] = max(maxr[i - 1], sum[i]);
ans = max(ans, sum[i] - minr[i]);
}
if (k >= 2)
ans = max(ans,
max(sum[n] - minr[n] + maxr[n],
sum[n] - minr[n] + maxr[n] + (k - 2) * sum[n]
)
);
return (int)(ans % mod);
}
};
空间复杂度O(1)就可以,最后更新答案只用到了pre[n]/maxr[n]/minr[n]。