Maximum subarray sum in an array created after repeated concatenation

Last Updated : 02 Nov, 2024

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

Naive Approach - O(nk) Time and O(nk) Space

A simple solution is to create an array of size n*k, then run Kadane's algorithm for the whole array.

Expected Approach - O(nk) Time and O(1) Space

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

Below is the implementation:

C++

#include <bits/stdc++.h> using namespace std; // Returns sum of maximum sum subarray created // after concatenating a[0..n-1] k times. int maxSubArraySumRepeated(vector<int>& arr, int k) {  int n = arr.size();  int maxSoFar = INT_MIN, maxEndingHere = 0;  for (int i = 0; i < n * k; i++) {    // Use modular arithmetic to get the next element  maxEndingHere += arr[i % n];  maxSoFar = max(maxSoFar, maxEndingHere);  if (maxEndingHere < 0)  maxEndingHere = 0;  }  return maxSoFar; } /* Driver program to test maxSubArraySum */ int main() {  vector<int> arr = {10, 20, -30, -1};  int k = 3;  cout << "Maximum contiguous sum is "  << maxSubArraySumRepeated(arr, k);  return 0; }

// Returns sum of maximum sum subarray created // after concatenating a[0..n-1] k times. #include <stdio.h> #include <limits.h> int maxSubArraySumRepeated(int arr[], int n, int k) {  int maxSoFar = INT_MIN, maxEndingHere = 0;  for (int i = 0; i < n * k; i++) {    // Use modular arithmetic to get the next element  maxEndingHere += arr[i % n];  if (maxEndingHere > maxSoFar) {  maxSoFar = maxEndingHere;  }  if (maxEndingHere < 0) {  maxEndingHere = 0;  }  }  return maxSoFar; } // Driver program to test maxSubArraySumRepeated int main() {  int arr[] = {10, 20, -30, -1};  int k = 3;  int n = sizeof(arr) / sizeof(arr[0]);  printf("Maximum contiguous sum is %d\n", maxSubArraySumRepeated(arr, n, k));  return 0; }

Java

// Returns sum of maximum sum subarray created // after concatenating a[0..n-1] k times. public class GfG {  public static int maxSubArraySumRepeated(int[] arr, int k) {  int n = arr.length;  int maxSoFar = Integer.MIN_VALUE, maxEndingHere = 0;  for (int i = 0; i < n * k; i++) {    // Use modular arithmetic to get the next element  maxEndingHere += arr[i % n];  maxSoFar = Math.max(maxSoFar, maxEndingHere);  if (maxEndingHere < 0)  maxEndingHere = 0;  }  return maxSoFar;  }  // Driver program to test maxSubArraySumRepeated  public static void main(String[] args) {  int[] arr = {10, 20, -30, -1};  int k = 3;  System.out.println("Maximum contiguous sum is " + maxSubArraySumRepeated(arr, k));  } }

Python

# Returns sum of maximum sum subarray created # after concatenating a[0..n-1] k times. def max_subarray_sum_repeated(arr, k): n = len(arr) max_so_far = float('-inf') max_ending_here = 0 for i in range(n * k): # Use modular arithmetic to get the next element max_ending_here += arr[i % n] max_so_far = max(max_so_far, max_ending_here) if max_ending_here < 0: max_ending_here = 0 return max_so_far # Driver program to test max_subarray_sum_repeated arr = [10, 20, -30, -1] k = 3 print("Maximum contiguous sum is", max_subarray_sum_repeated(arr, k))

// Returns sum of maximum sum subarray created // after concatenating a[0..n-1] k times. using System; using System.Linq; class Program {  public static int MaxSubArraySumRepeated(int[] arr, int k) {  int n = arr.Length;  int maxSoFar = int.MinValue, maxEndingHere = 0;  for (int i = 0; i < n * k; i++) {    // Use modular arithmetic to get the next element  maxEndingHere += arr[i % n];  maxSoFar = Math.Max(maxSoFar, maxEndingHere);  if (maxEndingHere < 0)  maxEndingHere = 0;  }  return maxSoFar;  }  // Driver program to test MaxSubArraySumRepeated  static void Main() {  int[] arr = {10, 20, -30, -1};  int k = 3;  Console.WriteLine("Maximum contiguous sum is " + MaxSubArraySumRepeated(arr, k));  } }

JavaScript

// Returns sum of maximum sum subarray created // after concatenating a[0..n-1] k times. function maxSubArraySumRepeated(arr, k) {  let n = arr.length;  let maxSoFar = Number.MIN_SAFE_INTEGER, maxEndingHere = 0;  for (let i = 0; i < n * k; i++) {    // Use modular arithmetic to get the next element  maxEndingHere += arr[i % n];  maxSoFar = Math.max(maxSoFar, maxEndingHere);  if (maxEndingHere < 0)  maxEndingHere = 0;  }  return maxSoFar; } // Driver program to test maxSubArraySumRepeated let arr = [10, 20, -30, -1]; let k = 3; console.log("Maximum contiguous sum is " + maxSubArraySumRepeated(arr, k));