PROBLEM LINK:Author: Hruday Pabbisetty DIFFICULTY:EASY PREREQUISITES:None PROBLEM:You are given array $A_0, \dots, A_{N1}$ 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 EXPLANATIONAnswer is maximum sum subarray from doubled $A$ plus either $0$ or $K2$ 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 $K2$ 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 $N1$ 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 $K2$, otherwise you add it with coefficient $0$. That gives you $O(N)$ solution. Example of code to find maximum subarray sum:
With this code you can find the solution as follows:
AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 11 Jan '18, 02:12

if(SOE(A) > 0) { answer = {prefix + SOE(A)*(k2) + suffix}. } else { answer = {prefix + suffix}. }
answered 16 Jan '18, 13:43

how to calculate prefix and suffix and also what they mean answered 16 Jan '18, 16:10

Would this not be able to calculate the maximum subarray sum too?
answered 16 Jan '18, 06:58

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? answered 25 Jan '18, 21:13
