KCON - Editorial

PROBLEM LINK:

Practice
Contest

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.

RELATED PROBLEMS:

Can someone please explain it in simple words?

Would this not be able to calculate the maximum subarray sum too?

dp[i] = max(dp[i-1]+arr2[i],arr2[i]+arr2[i-1]);

@nikmul19

      Your problem is to find the maximum sub array of B. Maximum SubArray of an array A is a continuous SubArray within the array A that has the largest Sum. For e.g.. In a array having elements {-25 , 20, -3, -16, -23, 18, 20, -7, 12, -5, -22} (Index starts with 0) the Maximum SubArray is from index 5 to index 8 which has a sum of 43. No other continuous SubArray within A would have sum which exceeds 43. The best method for finding Maximum SubArray is [Kadanae's algorithm][1].

     Okay now let's jump into the problem. Here you have to find the Maximum SubArray for an array B which is a k-times repetitive array of A. For e.g.. if A is {3, 2, -1} and K is 3 then B will be {3, 2, -1, 3, 2, -1, 3, 2, -1}. 

     First method: 
            You can create a  array B using A and you can deploy Kadanae's algorithm on it to find the maximum SubArray. But it's not a good solution. Array A can have upto 10^5 elements and K can also have value upto 10^5. So the size of the array B will be very large and it's a waste of memory to create an array B.

    Optimised Method:
            The maximum SubArray of B can be the sum of all its elements. For e.g.. if A is {3, 2, -1} and K is 3, then B will be {3, 2, -1, 3, 2, -1, 3, 2, -1}. The sum of all the elements in B will give us 12. To find this one we don't need to create the array B. We can simply find the sum of all the elements in array A and we can mutilply it with K. i.e (sum of elements in A)*k, Since B is the k-time repetition of the array A. Okay now we found out that the maximum SubArray of B is 12. 
           Oh Wait Wait we have just made that one wrong. Look at the array B carefully, we can omit the last term in it so that the sum will become 13. For this one The author uses prefix and suffix calculations. You can clearly understand with this example. Now array A is {-1, -2, 8, 9, 10, -2, -1} and consider K is 10. A is repeated 10 times in B. Consider the first repetition of A is A1, second is A2 and so on. So now our B array will be {A1, A2, A3, A4, A5, A6, A7, A8, A9, A10}. By finding only the (sum of elements in A)*k you will get the answer 270. But if you omit the first two elements in A1 and the last two elements in A10, You will get the Maximum SubArray as 276. So here we can check whether it is possible to omit some initial elements in A1 and some Final elements in A10. So the author is using prefix and suffix variables for that to calculate the sum of A1 and A10 specifically and he adds the remaining elements i.e answer = {prefix + SOE(A2) + SOE(A3) + SOE(A4) + SOE(A5) + SOE(A6) + SOE(A7) + SOE(A8) + SOE(A9) + suffix} , which in simplified form becomes {prefix + SOE(A)*(k-2) + suffix}. This is what he does. 
         SOE - Sum Of Elements. If SOE is positive then do this above calculation. Else just add the prefix and suffix.

if(SOE(A) > 0)

{

answer = {prefix + SOE(A)*(k-2) + suffix}.

}

else

{

answer = {prefix + suffix}.

}

       Now consider this test case. consider A as {12, -200, 12} and K is 3. Now the total sum becomes -ve. Look at B {12, -200, 12, 12, -200, 12, 12, -200, 12} i.e {A1, A2, A3}. Here the prefix will be 12 and suffix will also be 12. so the answer will be 24 which is the sum that exists at indexes 2 and 3, and indexes 5 and 6.
6 Likes

how to calculate prefix and suffix
and also what they mean

1 Like

Thanks @pazhamalai

Author’s solution is giving access denied

what about when all numbers are zero consider -3 -1 -2 and k = 3
in this case what will be suffix and prefix? And according to the @pazhamalai explanation what should be the answer?

Try this test case
1
3 2
7 -8 4