Maximum subarray sum in array formed by repeating the given array k times
Last Updated : 17 Feb, 2023
Given an integer k and an integer array arr[] of n elements, the task is to find the largest sub-array sum in the modified array (formed by repeating the given array k times). For example, if arr[] = {1, 2} and k = 3 then the modified array will be {1, 2, 1, 2, 1, 2}.
Examples:
Input: arr[] = {1, 2}, k = 3
Output: 9
Modified array will be {1, 2, 1, 2, 1, 2}
And the maximum sub-array sum will be 1 + 2 + 1 + 2 + 1 + 2 = 9
Input: arr[] = {1, -2, 1}, k = 5
Output: 2
A simple solution is to create an array of size n * k, then run Kadane's algorithm to find the maximum sub-array sum.
C++ // C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum // subarray sum of arr[] long maxSubArrSum(vector<int>& a, int len) { int size = len; int max_so_far = INT_MIN; long max_ending_here = 0; for (int i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; 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; } // Function to return the maximum sub-array // sum of the modified array long maxSubKSum(vector<int>& arr, int k, int len) { vector<int> res; while (k--) { for (int i = 0; i < len; i++) { res.push_back(arr[i]); } } return maxSubArrSum(res, res.size()); } // Driver code int main() { vector<int> arr = { 1, 2 }; int arrlen = arr.size(); int k = 3; cout << maxSubKSum(arr, k, arrlen) << endl; return 0; } import java.util.*; import java.io.*; import java.util.List; public class Gfg { // Function to return the maximum subarray sum of arr[] public static long maxSubArrSum(List<Integer> a, int len) { int size = len; long maxSoFar = Integer.MIN_VALUE; long maxEndingHere = 0; for (int i = 0; i < size; i++) { maxEndingHere = maxEndingHere + a.get(i); if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere; if (maxEndingHere < 0) maxEndingHere = 0; } return maxSoFar; } // Function to return the maximum sub-array sum of the // modified array public static long maxSubKSum(List<Integer> arr, int k, int len) { List<Integer> res = new ArrayList<>(); while (k-- > 0) { for (int i = 0; i < len; i++) { res.add(arr.get(i)); } } return maxSubArrSum(res, res.size()); } // Driver code public static void main(String[] args) { List<Integer> arr = Arrays.asList(1, 2); int arrlen = arr.size(); int k = 3; System.out.println(maxSubKSum(arr, k, arrlen)); } } using System; using System.Collections.Generic; class Gfg { // Function to return the maximum subarray sum of arr[] public static long maxSubArrSum(List<int> a, int len) { int size = len; long maxSoFar = int.MinValue; long maxEndingHere = 0; for (int i = 0; i < size; i++) { maxEndingHere = maxEndingHere + a[i]; if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere; if (maxEndingHere < 0) maxEndingHere = 0; } return maxSoFar; } // Function to return the maximum sub-array // sum of the modified array public static long maxSubKSum(List<int> arr, int k, int len) { List<int> res = new List<int>(); while (k-- > 0) { for (int i = 0; i < len; i++) { res.Add(arr[i]); } } return maxSubArrSum(res, res.Count); } // Driver code public static void Main(string[] args) { List<int> arr = new List<int>() { 1, 2 }; int arrlen = arr.Count; int k = 3; Console.WriteLine(maxSubKSum(arr, k, arrlen)); } } // Javascript implementation of the approach // Function to return the maximum // subarray sum of arr[] function maxSubArrSum(a, len) { let size = len; let max_so_far = Number.MIN_SAFE_INTEGER; let max_ending_here = 0; for (let i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; 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; } // Function to return the maximum sub-array // sum of the modified array function maxSubKSum(arr, k, len) { let res=[]; while (k--) { for (let i = 0; i < len; i++) { res.push(arr[i]); } } return maxSubArrSum(res, res.length); } // Driver code let arr = [ 1, 2 ]; let arrlen = arr.length; let k = 3; console.log(maxSubKSum(arr, k, arrlen)); # Python implementation of the approach # Import the sys module to handle the max size of an integer import sys def maxSubArrSum(a, len): """ Returns the maximum subarray sum of arr[] Arguments: a -- list of integers len -- length of the list Returns: long -- maximum subarray sum """ size = len max_so_far = -sys.maxsize-1 max_ending_here = 0 for i in range(size): max_ending_here += a[i] 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 def maxSubKSum(arr, k, len): """ Returns the maximum sub-array sum of the modified array Arguments: arr -- list of integers k -- number of times the array is repeated len -- length of the original array Returns: long -- maximum sub-array sum of the modified array """ res = [] for i in range(k): for j in range(len): res.append(arr[j]) return maxSubArrSum(res, len * k) if __name__ == "__main__": arr = [1, 2] arrlen = len(arr) k = 3 print(maxSubKSum(arr, k, arrlen))
Time Complexity: O(n * k)
Auxiliary Space: O(n * k)
A better solution is to calculate the sum of the array arr[] and store it in sum.
- If sum < 0 then calculate the maximum sub-array sum of an array formed by concatenating the array two times irrespective of the K. For example, take arr[] = {1, -4, 1} and k = 5. The sum of the array is less than 0. So, the maximum sub-array sum of the array can be found after concatenating the array two times only irrespective of the value of K i.e. b[] = {1, -4, 1, 1, -4, 1} and the maximum sub-array sum = 1 + 1 = 2
- If sum > 0 then maximum sub-array will include the maximum sum as calculated in the previous step (where the array was concatenated twice) + the rest (k - 2) repetitions of the array can also be included as their sum is greater than 0 that will contribute to the maximum sum.
Below is the implementation of the above approach:
C++ // C++ implementation of the approach #include<bits/stdc++.h> using namespace std; // Function to concatenate array void arrayConcatenate(int *arr, int *b, int k,int len) { // Array b will be formed by concatenation // array a exactly k times int j = 0; while (k > 0) { for (int i = 0; i < len; i++) { b[j++] = arr[i]; } k--; } } // Function to return the maximum // subarray sum of arr[] long maxSubArrSum(int *a,int len) { int size = len; int max_so_far = INT_MIN; long max_ending_here = 0; for (int i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; 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; } // Function to return the maximum sub-array // sum of the modified array long maxSubKSum(int *arr, int k,int len) { int arrSum = 0; long maxSubArrSum1 = 0; int b[(2 * len)]={0}; // Concatenating the array 2 times arrayConcatenate(arr, b, 2,len); // Finding the sum of the array for (int i = 0; i < len; i++) arrSum += arr[i]; // If sum is less than zero if (arrSum < 0) maxSubArrSum1 = maxSubArrSum(b,2*len); // If sum is greater than zero else maxSubArrSum1 = maxSubArrSum(b,2*len) + (k - 2) * arrSum; return maxSubArrSum1; } // Driver code int main() { int arr[] = { 1, -2, 1 }; int arrlen=sizeof(arr)/sizeof(arr[0]); int k = 5; cout << maxSubKSum(arr, k,arrlen) << endl; return 0; } // This code is contributed by mits // Java implementation of the approach public class GFG { // Function to concatenate array static void arrayConcatenate(int arr[], int b[], int k) { // Array b will be formed by concatenation // array a exactly k times int j = 0; while (k > 0) { for (int i = 0; i < arr.length; i++) { b[j++] = arr[i]; } k--; } } // Function to return the maximum // subarray sum of arr[] static int maxSubArrSum(int a[]) { int size = a.length; int max_so_far = Integer.MIN_VALUE, max_ending_here = 0; for (int i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; 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; } // Function to return the maximum sub-array // sum of the modified array static long maxSubKSum(int arr[], int k) { int arrSum = 0; long maxSubArrSum = 0; int b[] = new int[(2 * arr.length)]; // Concatenating the array 2 times arrayConcatenate(arr, b, 2); // Finding the sum of the array for (int i = 0; i < arr.length; i++) arrSum += arr[i]; // If sum is less than zero if (arrSum < 0) maxSubArrSum = maxSubArrSum(b); // If sum is greater than zero else maxSubArrSum = maxSubArrSum(b) + (k - 2) * arrSum; return maxSubArrSum; } // Driver code public static void main(String[] args) { int arr[] = { 1, -2, 1 }; int k = 5; System.out.println(maxSubKSum(arr, k)); } } # Python approach to this problem # A python module where element # are added to list k times def MaxsumArrKtimes(c, ktimes): # Store element in list d k times d = c * ktimes # two variable which can keep # track of maximum sum seen # so far and maximum sum ended. maxsofar = -99999 maxending = 0 for i in d: maxending = maxending + i if maxsofar < maxending: maxsofar = maxending if maxending < 0: maxending = 0 return maxsofar # Get the Maximum sum of element print(MaxsumArrKtimes([1, -2, 1], 5)) # This code is contributed by AnupGaurav.
// C# implementation of the approach using System; class GFG { // Function to concatenate array static void arrayConcatenate(int []arr, int []b, int k) { // Array b will be formed by concatenation // array a exactly k times int j = 0; while (k > 0) { for (int i = 0; i < arr.Length; i++) { b[j++] = arr[i]; } k--; } } // Function to return the maximum // subarray sum of arr[] static int maxSubArrSum(int []a) { int size = a.Length; int max_so_far = int.MinValue, max_ending_here = 0; for (int i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; 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; } // Function to return the maximum sub-array // sum of the modified array static long maxSubKSum(int []arr, int k) { int arrSum = 0; long maxSubArrsum = 0; int []b = new int[(2 * arr.Length)]; // Concatenating the array 2 times arrayConcatenate(arr, b, 2); // Finding the sum of the array for (int i = 0; i < arr.Length; i++) arrSum += arr[i]; // If sum is less than zero if (arrSum < 0) maxSubArrsum = maxSubArrSum(b); // If sum is greater than zero else maxSubArrsum = maxSubArrSum(b) + (k - 2) * arrSum; return maxSubArrsum; } // Driver code public static void Main() { int []arr = { 1, -2, 1 }; int k = 5; Console.WriteLine(maxSubKSum(arr, k)); } } // This code is contributed by Ryuga <?php // PHP implementation of the approach // Function to concatenate array function arrayConcatenate(&$arr, &$b, $k) { // Array b will be formed by concatenation // array a exactly k times $j = 0; while ($k > 0) { for ($i = 0; $i < sizeof($arr); $i++) { $b[$j++] = $arr[$i]; } $k--; } } // Function to return the maximum // subarray sum of arr[] function maxSubArrSum(&$a) { $size = sizeof($a); $max_so_far = 0; $max_ending_here = 0; for ($i = 0; $i < $size; $i++) { $max_ending_here = $max_ending_here + $a[$i]; 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; } // Function to return the maximum sub-array // sum of the modified array function maxSubKSum(&$arr,$k) { $arrSum = 0; $maxSubArrSum = 0; $b = array_fill(0,(2 * sizeof($arr)),NULL); // Concatenating the array 2 times arrayConcatenate($arr, $b, 2); // Finding the sum of the array for ($i = 0; $i < sizeof($arr); $i++) $arrSum += $arr[$i]; // If sum is less than zero if ($arrSum < 0) $maxSubArrSum = maxSubArrSum($b); // If sum is greater than zero else $maxSubArrSum = maxSubArrSum($b) + ($k - 2) * $arrSum; return $maxSubArrSum; } // Driver code $arr = array(1, -2, 1 ); $k = 5; echo maxSubKSum($arr, $k); // This code is contributed by Ita_c. ?> <script> // Javascript implementation of the approach // Function to concatenate array function arrayConcatenate(arr,b,k) { // Array b will be formed by concatenation // array a exactly k times let j = 0; while (k > 0) { for (let i = 0; i < arr.length; i++) { b[j++] = arr[i]; } k--; } } // Function to return the maximum // subarray sum of arr[] function maxSubArrSum(a) { let size = a.length; let max_so_far = Number.MIN_VALUE, max_ending_here = 0; for (let i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; 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; } // Function to return the maximum sub-array // sum of the modified array function maxSubKSum(arr,k) { let arrSum = 0; let maxsubArrSum = 0; let b = new Array(2 * arr.length); // Concatenating the array 2 times arrayConcatenate(arr, b, 2); // Finding the sum of the array for (let i = 0; i < arr.length; i++) arrSum += arr[i]; // If sum is less than zero if (arrSum < 0) maxsubArrSum = maxSubArrSum(b); // If sum is greater than zero else maxsubArrSum = maxSubArrSum(b) + (k - 2) * arrSum; return maxsubArrSum; } // Driver code let arr=[ 1, -2, 1 ]; let k = 5; document.write(maxSubKSum(arr, k)); // This code is contributed by rag2127 </script> Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(N)
Similar Reads
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 = 2Output : 59After concatenating array twice, we get {-1, 10, 20, -1, 10, 20} which has maximum subarray sum
4 min read
Maximum length of same indexed subarrays from two given arrays satisfying the given condition Given two arrays arr[] and brr[] and an integer C, the task is to find the maximum possible length, say K, of the same indexed subarrays such that the sum of the maximum element in the K-length subarray in brr[] with the product between K and sum of the K-length subarray in arr[] does not exceed C.
15+ min read
Maximum subarray sum in an array created after repeated concatenation | Set-2 Given an array arr[] consisting of N integers and a positive integer K, the task is to find the largest sum of any contiguous subarray in the modified array formed by repeating the given array K times. Examples: Input: arr[] = {-1, 10, 20}, K = 2Output: 59Explanation:After concatenating the array tw
15+ min read
Maximize the minimum value of Array by performing given operations at most K times Given array A[] of size N and integer K, the task for this problem is to maximize the minimum value of the array by performing given operations at most K times. In one operation choose any index and increase that array element by 1. Examples: Input: A[] = {3, 1, 2, 4, 6, 2, 5}, K = 8Output: 4Explana
10 min read
Maximum sum obtained by dividing Array into several subarrays as per given conditions Given an array arr[] of size N, the task is to calculate the maximum sum that can be obtained by dividing the array into several subarrays(possibly one), where each subarray starting at index i and ending at index j (j>=i) contributes arr[j]-arr[i] to the sum. Examples: Input: arr[]= {1, 5, 3}, N
5 min read
Maximum subarray sum possible after removing at most K array elements Given an array arr[] of size N and an integer K, the task is to find the maximum subarray sum by removing at most K elements from the array. Examples: Input: arr[] = { -2, 1, 3, -2, 4, -7, 20 }, K = 1 Output: 26 Explanation: Removing arr[5] from the array modifies arr[] to { -2, 1, 3, -2, 4, 20 } Su
15+ min read