classSolution {
public:int kConcatenationMaxSum(vector<int>& arr, int k) {
int mod =1e9+7;
long sum =0, max_sum =0, cur =0;
for (int x : arr) {
sum += x;
cur = max((long)x, cur + x);
max_sum = max(max_sum, cur);
}
long prefix =0, s =0;
for (int x : arr) {
s += x;
prefix = max(prefix, s);
}
long suffix =0; s =0;
for (int i = arr.size()-1; i >=0; --i) {
s += arr[i];
suffix = max(suffix, s);
}
if (k ==1) return max_sum % mod;
long ans = max(max_sum, prefix + suffix + max(0L, sum)*(k-2));
return ans % mod;
}
};
classSolution {
publicintkConcatenationMaxSum(int[] arr, int k) {
int mod = 1000000007;
long sum = 0, maxSum = 0, cur = 0;
for (int x : arr) {
sum += x;
cur = Math.max(x, cur + x);
maxSum = Math.max(maxSum, cur);
}
long prefix = 0, s = 0;
for (int x : arr) {
s += x;
prefix = Math.max(prefix, s);
}
long suffix = 0; s = 0;
for (int i = arr.length-1; i >= 0; --i) {
s += arr[i];
suffix = Math.max(suffix, s);
}
if (k == 1) return (int)(maxSum % mod);
long ans = Math.max(maxSum, prefix + suffix + Math.max(0, sum)*(k-2));
return (int)(ans % mod);
}
}
classSolution {
funkConcatenationMaxSum(arr: IntArray, k: Int): Int {
val mod = 1000000007var sum = 0L; var maxSum = 0L; var cur = 0Lfor (x in arr) {
sum += x
cur = maxOf(x.toLong(), cur + x)
maxSum = maxOf(maxSum, cur)
}
var prefix = 0L; var s = 0Lfor (x in arr) {
s += x
prefix = maxOf(prefix, s)
}
var suffix = 0L; s = 0Lfor (i in arr.indices.reversed()) {
s += arr[i]
suffix = maxOf(suffix, s)
}
if (k ==1) return (maxSum % mod).toInt()
val ans = maxOf(maxSum, prefix + suffix + maxOf(0L, sum)*(k-2))
return (ans % mod).toInt()
}
}
classSolution:
defkConcatenationMaxSum(self, arr: list[int], k: int) -> int:
mod =10**9+7defkadane(a):
cur = ans =0for x in a:
cur = max(x, cur+x)
ans = max(ans, cur)
return ans
total = sum(arr)
prefix = suffix = s =0for x in arr:
s += x
prefix = max(prefix, s)
s =0for x in arr[::-1]:
s += x
suffix = max(suffix, s)
if k ==1:
return kadane(arr) % mod
ans = max(kadane(arr*2), prefix + suffix + max(0, total)*(k-2))
return ans % mod