class Solution {
public:
int kConcatenationMaxSum(vector<int>& arr, int k) {
}
};
1191. K 次串联后最大子数组之和
给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。
例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。
返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
由于 结果可能会很大，需要返回的 109 + 7 的 模 。
示例 1：
输入：arr = [1,2], k = 3 输出：9
示例 2：
输入：arr = [1,-2,1], k = 5 输出：2
示例 3：
输入：arr = [-1,-2], k = 7 输出：0
提示：
1 <= arr.length <= 1051 <= k <= 105-104 <= arr[i] <= 104原站题解
cpp 解法, 执行用时: 48 ms, 内存消耗: 38.5 MB, 提交时间: 2023-07-01 14:12:16
class Solution {
public:
int kConcatenationMaxSum(vector<int>& arr, int k) {
int n = arr.size();
long long prefix = INT64_MIN, suffix = INT64_MIN;
long long maxval = INT64_MIN, sum = 0, factor = 1e9 + 7;
long long preval = 0;
for (int i = 0; i < n; ++i) {
sum += arr[i];
prefix = max(sum, prefix);
if (preval > 0)
preval += arr[i];
else
preval = arr[i];
maxval = max(maxval, preval);
}
sum = 0;
for (int i = n; i-- > 0; ) {
sum += arr[i];
suffix = max(sum, suffix);
}
maxval = max(maxval, (long long) 0);
if (k == 1)
return maxval % factor;
long long v0 = sum * (k - 2) + prefix + suffix;
long long v1 = prefix + suffix;
maxval = max(maxval, max(v0, v1));
return maxval % factor;
}
};
python3 解法, 执行用时: 156 ms, 内存消耗: 27.5 MB, 提交时间: 2023-07-01 14:11:24
class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
acc, m = 0, 0
for _ in range(min(k, 2)):
for n in arr:
acc= max(0, acc)+n
m = max(m, acc)
return (m if k==1 else m+ max(sum(arr) *(k - 2) , 0)) % (10**9 + 7)
python3 解法, 执行用时: 116 ms, 内存消耗: 30.9 MB, 提交时间: 2023-07-01 14:10:21
class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
n = len(arr)
s, d = [0] * (n + 1), [0] * n
for i in range(n):
s[i + 1] = s[i] + arr[i] #前缀和
d[i] = max(d[i - 1] + arr[i], 0)#最大连续和
if k == 1:
return max(d) #如果只有一个周期，就直接输出最大的连续和
return max(max(d), max(s[n], 0) * (k - 2) + s[n] - min(s) + max(s)) % 1000000007
#比较一个周期的最大连续和以及多个周期的总和大小
java 解法, 执行用时: 3 ms, 内存消耗: 55.3 MB, 提交时间: 2023-07-01 14:09:36
class Solution {
public int kConcatenationMaxSum(int[] arr, int k) {
if (arr == null || arr.length == 0) return 0;
long maxOfEnd = arr[0] > 0 ? arr[0] : 0L, maxSoFar = maxOfEnd, sum = arr[0];
for (int i = 1; i < Math.min(k, 2) * arr.length; i++) {
maxOfEnd = Math.max(maxOfEnd + arr[i % arr.length], arr[i % arr.length]);
maxSoFar = Math.max(maxOfEnd, maxSoFar);
if (i < arr.length) sum += arr[i];
}
while (sum > 0 && --k >= 2)
maxSoFar = (maxSoFar + sum) % 1000000007;
return (int) maxSoFar % 1000000007;
}
}
golang 解法, 执行用时: 48 ms, 内存消耗: 8.6 MB, 提交时间: 2023-07-01 14:08:31
var mod int = int(1e9)+7
func kConcatenationMaxSum(arr []int, k int) int {
n := len(arr)
if n == 0 {
return 0
}
var (
maxSoFar int
maxCur int
sum = arr[0]
)
if arr[0] > 0 {
maxSoFar, maxCur = arr[0], arr[0]
}
// 如果k小于2 的话，这个循环计算的就是单个数组内子数组最大和
// 如果k大于2 ，这个循环计算的就是最大子数组和横跨两个数组时，单个数组内最大前缀和加上最大后缀和
for i := 1; i < min(k, 2)*n; i++ {
maxCur = max(maxCur+arr[i%n], arr[i%n])
maxSoFar = max(maxCur, maxSoFar)
if i < n {
sum += arr[i]
}
}
if sum > 0 {
for k > 2 {
maxSoFar += sum
k--
}
}
return maxSoFar % mod
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
golang 解法, 执行用时: 48 ms, 内存消耗: 8.6 MB, 提交时间: 2023-07-01 14:07:53
// lsum: 从左侧开始的最大子数组和
// rsum: 从右侧开始的最大子数组和
// sum: 最大子数组和
// allsum: 数组和
// 答案来自以下三种之一，k=1单独判断
// lsum + rsum
// sum
// rsum + lsum + (k-2)*allsum
var mod int = int(1e9)+7
func kConcatenationMaxSum(arr []int, k int) int {
n := len(arr)
lsum := int64(arr[n-1])
sum := int64(arr[n-1])
allsum := int64(arr[n-1])
for i:=n-2;i>=0;i--{
lsum = max(int64(arr[i]), int64(arr[i]) +lsum)
sum = max(sum, lsum)
allsum += int64(arr[i])
}
rsum := int64(arr[0])
for i:=1;i<n;i++{
rsum = max(int64(arr[i]), int64(arr[i])+rsum)
}
lsum = max(0, lsum)
rsum = max(0, rsum)
sum = max(0, sum)
if k == 1{
return int(sum)
}
a := lsum + rsum
b := allsum * int64(k)
c := (rsum + lsum) + allsum * int64(k-2)
return int(max(sum, max(a, max(b, c)))) % mod
}
func max(a,b int64)int64{
if a>b{
return a
}
return b
}