# Maximum subarray sum in an array created after repeated concatenation

Given an array and a number k, find the largest sum of contiguous array in the modified array which is formed by repeating the given array k times.

Examples :

```Input  : arr[] = {-1, 10, 20}, k = 2
Output : 59
After concatenating array twice, we
get {-1, 10, 20, -1, 10, 20} which has
maximum subarray sum as 59.

Input  : arr[] = {-1, -2, -3}, k = 3
Output : -1
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A simple solution is to create an array of size n*k, then run Kadane’s algorithm. Time complexity would be O(nk) and auxiliary space would be O(n*k)

A better solution is to run a loop on same array and use modular arithmetic to move back beginning after end of array.

## C++

 `// C++ program to print largest contiguous ` `// array sum when array is created after ` `// concatenating a small array k times. ` `#include ` `using` `namespace` `std; ` ` `  `// Returns sum of maximum sum subarray created ` `// after concatenating a[0..n-1] k times. ` `int` `maxSubArraySumRepeated(``int` `a[], ``int` `n, ``int` `k) ` `{ ` `    ``int` `max_so_far = INT_MIN, max_ending_here = 0; ` ` `  `    ``for` `(``int` `i = 0; i < n*k; i++) ` `    ``{ ` `        ``// This is where it differs from Kadane's ` `        ``// algorithm. We use modular arithmetic to ` `        ``// find next element. ` `        ``max_ending_here = max_ending_here + a[i%n]; ` ` `  `        ``if` `(max_so_far < max_ending_here) ` `            ``max_so_far = max_ending_here; ` ` `  `        ``if` `(max_ending_here < 0) ` `            ``max_ending_here = 0; ` `    ``} ` `    ``return` `max_so_far; ` `} ` ` `  `/*Driver program to test maxSubArraySum*/` `int` `main() ` `{ ` `    ``int` `a[] = {10, 20, -30, -1}; ` `    ``int` `n = ``sizeof``(a)/``sizeof``(a[0]); ` `    ``int` `k = 3; ` `    ``cout << ``"Maximum contiguous sum is "` `         ``<< maxSubArraySumRepeated(a, n, k); ` `    ``return` `0; ` `} `

## Java

 `// Java program to print largest contiguous ` `// array sum when array is created after ` `// concatenating a small array k times. ` `import` `java.io.*; ` ` `  `class` `GFG { ` `     `  `// Returns sum of maximum sum  ` `// subarray created after  ` `// concatenating a[0..n-1] k times. ` `static` `int` `maxSubArraySumRepeated(``int` `a[], ` `                             ``int` `n, ``int` `k) ` `{ ` `    ``int` `max_so_far = ``0``; ` `    ``int` `INT_MIN, max_ending_here=``0``; ` ` `  `    ``for` `(``int` `i = ``0``; i < n*k; i++) ` `    ``{ ` `        ``// This is where it differs from  ` `        ``// Kadane's algorithm. We use modular ` `        ``//  arithmetic to find next element. ` `        ``max_ending_here = max_ending_here + ` `                                    ``a[i % n]; ` ` `  `        ``if` `(max_so_far < max_ending_here) ` `            ``max_so_far = max_ending_here; ` ` `  `        ``if` `(max_ending_here < ``0``) ` `            ``max_ending_here = ``0``; ` `    ``} ` `    ``return` `max_so_far; ` `} ` ` `  `// Driver program to test maxSubArraySum ` `public` `static` `void` `main (String[] args) { ` `     `  `    ``int` `a[] = {``10``, ``20``, -``30``, -``1``}; ` `    ``int` `n = a.length; ` `    ``int` `k = ``3``; ` `     `  `    ``System.out.println(``"Maximum contiguous sum is "` `                   ``+ maxSubArraySumRepeated(a, n, k)); ` `} ` ` `  `} ` `     `  `// This code is contributed by vt_m `

## Python3

 `# Python program to print ` `# largest contiguous ` `# array sum when array ` `# is created after ` `# concatenating a small ` `# array k times. ` ` `  `# Returns sum of maximum ` `# sum subarray created ` `# after concatenating ` `# a[0..n-1] k times. ` `def` `maxSubArraySumRepeated(a, n, k): ` ` `  `    ``max_so_far ``=` `-``2147483648` `    ``max_ending_here ``=` `0` `  `  `    ``for` `i ``in` `range``(n``*``k): ` `     `  `        ``# This is where it ` `        ``# differs from Kadane's ` `        ``# algorithm. We use ` `        ``#  modular arithmetic to ` `        ``# find next element. ` `        ``max_ending_here ``=` `max_ending_here ``+` `a[i``%``n] ` `  `  `        ``if` `(max_so_far < max_ending_here): ` `            ``max_so_far ``=` `max_ending_here ` `  `  `        ``if` `(max_ending_here < ``0``): ` `            ``max_ending_here ``=` `0` `     `  `    ``return` `max_so_far ` `  `  `# Driver program ` `# to test maxSubArraySum ` ` `  `a ``=` `[``10``, ``20``, ``-``30``, ``-``1``] ` `n ``=` `len``(a) ` `k ``=` `3` ` `  `print``(``"Maximum contiguous sum is "``, ` `    ``maxSubArraySumRepeated(a, n, k)) ` ` `  `# This code is contributed ` `# by Anant Agarwal. `

## C#

 `// C# program to print largest contiguous ` `// array sum when array is created after ` `// concatenating a small array k times. ` `using` `System; ` ` `  `class` `GFG { ` `     `  `// Returns sum of maximum sum  ` `// subarray created after  ` `// concatenating a[0..n-1] k times. ` `static` `int` `maxSubArraySumRepeated(``int` `[]a,  ` `                                  ``int` `n,  ` `                                  ``int` `k) ` `{ ` `    ``int` `max_so_far = 0; ` `    ``int` `max_ending_here=0; ` ` `  `    ``for` `(``int` `i = 0; i < n * k; i++) ` `    ``{ ` `        ``// This is where it differs from  ` `        ``// Kadane's algorithm. We use modular ` `        ``// arithmetic to find next element. ` `        ``max_ending_here = max_ending_here + ` `                                  ``a[i % n]; ` ` `  `        ``if` `(max_so_far < max_ending_here) ` `            ``max_so_far = max_ending_here; ` ` `  `        ``if` `(max_ending_here < 0) ` `            ``max_ending_here = 0; ` `    ``} ` `    ``return` `max_so_far; ` `} ` ` `  `// Driver Code ` `public` `static` `void` `Main () ` `{ ` `     `  `    ``int` `[]a = {10, 20, -30, -1}; ` `    ``int` `n = a.Length; ` `    ``int` `k = 3; ` `     `  `    ``Console.Write(``"Maximum contiguous sum is "` `                  ``+ maxSubArraySumRepeated(a, n, k)); ` `} ` `} ` `     `  `// This code is contributed by nitin mittal. `

## PHP

 ` `

Output :

`Maximum contiguous sum is 30`

Can we use the repeating property of array to get a better solution ?