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 arraylong 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 codeint 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 arrayfunction 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 codelet 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 integerimport sysdef 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_fardef 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)) |
Output
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 approachpublic 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 timesdef 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 elementprint(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 arrayfunction 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 arrayfunction 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 arrayfunction 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 arrayfunction 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 codelet arr=[ 1, -2, 1 ];let k = 5;document.write(maxSubKSum(arr, k));// This code is contributed by rag2127</script> |
Output
2
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!