PROBLEM LINK:
Author: Hruday Pabbisetty
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
You are given array A_0, \dots, A_{N-1} and integer K. Array B of size N \cdot K is formed by concatenating K copies of array A. You have to find maximum subarray sum of the array B.
QUICK EXPLANATION
Answer is maximum sum subarray from doubled A plus either 0 or K-2 sums of all elements in A.
EXPLANATION:
Let’s denote array A concatenated with itself as 2A. You should note that any subarray in array B can be presented as arbitrary subarray in 2A plus from 0 to K-2 whole arrays A. Indeed you begin in some position i, then swallow some whole number of arrays A then continue from position which corresponds to i+1 in 2A and swallow at most N-1 elements, thus you won’t leave array 2A. So first of all you should find subarray with largest sum in 2A, which you can do with prefix sums, Kadane’s algorithm or any other algorithm you may find in this wikipedia article. After that if sum of elements in A is positive, you add it with coefficient K-2, otherwise you add it with coefficient 0. That gives you O(N) solution.
Example of code to find maximum subarray sum:
const int64_t inf = 1e18;
int64_t sum = 0, mn = 0;
int64_t ans = -inf;
for(int i = 0; i < n; i++) {
sum += a[i];
ans = max(ans, sum - mn);
mn = min(mn, sum);
}
return ans;
With this code you can find the solution as follows:
if(k == 1) {
cout << maxsub(a) << endl;
} else {
int64_t sm = accumulate(begin(a), end(a), 0ll);
for(int i = 0; i < n; i++) {
a.push_back(a[i]);
}
int64_t ans = maxsub(a);
if(sm > 0) {
ans += sm * (k - 2);
}
cout << ans << endl;
}
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.