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++
#include <bits/stdc++.h>
using namespace std;
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;
}
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());
}
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 {
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;
}
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());
}
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 {
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;
}
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);
}
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
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 maxSubKSum(arr, k, len)
{
let res=[];
while (k--) {
for (let i = 0; i < len; i++) {
res.push(arr[i]);
}
}
return maxSubArrSum(res, res.length);
}
let arr = [ 1, 2 ];
let arrlen = arr.length;
let k = 3;
console.log(maxSubKSum(arr, k, arrlen));
|
Python3
import sys
def maxSubArrSum(a, len ):
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 ):
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++
#include<bits/stdc++.h>
using namespace std;
void arrayConcatenate( int *arr, int *b,
int k, int len)
{
int j = 0;
while (k > 0)
{
for ( int i = 0; i < len; i++)
{
b[j++] = arr[i];
}
k--;
}
}
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;
}
long maxSubKSum( int *arr, int k, int len)
{
int arrSum = 0;
long maxSubArrSum1 = 0;
int b[(2 * len)]={0};
arrayConcatenate(arr, b, 2,len);
for ( int i = 0; i < len; i++)
arrSum += arr[i];
if (arrSum < 0)
maxSubArrSum1 = maxSubArrSum(b,2*len);
else
maxSubArrSum1 = maxSubArrSum(b,2*len) +
(k - 2) * arrSum;
return maxSubArrSum1;
}
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;
}
|
Java
public class GFG {
static void arrayConcatenate( int arr[], int b[],
int k)
{
int j = 0 ;
while (k > 0 ) {
for ( int i = 0 ; i < arr.length; i++) {
b[j++] = arr[i];
}
k--;
}
}
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;
}
static long maxSubKSum( int arr[], int k)
{
int arrSum = 0 ;
long maxSubArrSum = 0 ;
int b[] = new int [( 2 * arr.length)];
arrayConcatenate(arr, b, 2 );
for ( int i = 0 ; i < arr.length; i++)
arrSum += arr[i];
if (arrSum < 0 )
maxSubArrSum = maxSubArrSum(b);
else
maxSubArrSum = maxSubArrSum(b) +
(k - 2 ) * arrSum;
return maxSubArrSum;
}
public static void main(String[] args)
{
int arr[] = { 1 , - 2 , 1 };
int k = 5 ;
System.out.println(maxSubKSum(arr, k));
}
}
|
Python3
def MaxsumArrKtimes(c, ktimes):
d = c * ktimes
maxsofar = - 99999
maxending = 0
for i in d:
maxending = maxending + i
if maxsofar < maxending:
maxsofar = maxending
if maxending < 0 :
maxending = 0
return maxsofar
print (MaxsumArrKtimes([ 1 , - 2 , 1 ], 5 ))
|
C#
using System;
class GFG
{
static void arrayConcatenate( int []arr,
int []b, int k)
{
int j = 0;
while (k > 0)
{
for ( int i = 0; i < arr.Length; i++)
{
b[j++] = arr[i];
}
k--;
}
}
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;
}
static long maxSubKSum( int []arr, int k)
{
int arrSum = 0;
long maxSubArrsum = 0;
int []b = new int [(2 * arr.Length)];
arrayConcatenate(arr, b, 2);
for ( int i = 0; i < arr.Length; i++)
arrSum += arr[i];
if (arrSum < 0)
maxSubArrsum = maxSubArrSum(b);
else
maxSubArrsum = maxSubArrSum(b) +
(k - 2) * arrSum;
return maxSubArrsum;
}
public static void Main()
{
int []arr = { 1, -2, 1 };
int k = 5;
Console.WriteLine(maxSubKSum(arr, k));
}
}
|
PHP
<?php
function arrayConcatenate(& $arr , & $b , $k )
{
$j = 0;
while ( $k > 0)
{
for ( $i = 0; $i < sizeof( $arr ); $i ++)
{
$b [ $j ++] = $arr [ $i ];
}
$k --;
}
}
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 maxSubKSum(& $arr , $k )
{
$arrSum = 0;
$maxSubArrSum = 0;
$b = array_fill (0,(2 * sizeof( $arr )),NULL);
arrayConcatenate( $arr , $b , 2);
for ( $i = 0; $i < sizeof( $arr ); $i ++)
$arrSum += $arr [ $i ];
if ( $arrSum < 0)
$maxSubArrSum = maxSubArrSum( $b );
else
$maxSubArrSum = maxSubArrSum( $b ) +
( $k - 2) * $arrSum ;
return $maxSubArrSum ;
}
$arr = array (1, -2, 1 );
$k = 5;
echo maxSubKSum( $arr , $k );
?>
|
Javascript
<script>
function arrayConcatenate(arr,b,k)
{
let j = 0;
while (k > 0) {
for (let i = 0; i < arr.length; i++) {
b[j++] = arr[i];
}
k--;
}
}
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 maxSubKSum(arr,k)
{
let arrSum = 0;
let maxsubArrSum = 0;
let b = new Array(2 * arr.length);
arrayConcatenate(arr, b, 2);
for (let i = 0; i < arr.length; i++)
arrSum += arr[i];
if (arrSum < 0)
maxsubArrSum = maxSubArrSum(b);
else
maxsubArrSum = maxSubArrSum(b) +
(k - 2) * arrSum;
return maxsubArrSum;
}
let arr=[ 1, -2, 1 ];
let k = 5;
document.write(maxSubKSum(arr, k));
</script>
|
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!