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.