Maximum subarray sum in array formed by repeating the given array k times
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 = 9Input: 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; } |
Java
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)); } } |
C#
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
// 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)); |
Python3
# 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)) |
9
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
// 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)); } } |
Python3
# 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#
// 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 // 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. ?> |
Javascript
<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> |
2
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(N)
Contact Us