Given an array arr[] of length N, the task is to find the largest sum contiguous subarray by adding an integer S exactly at K different positions in the array for every K from [0, N].
Examples:
Input: arr[] = {4, 1, 3, 2}, S = 2
Output: 10 12 14 16 18
Explanation:
For k = 0, the sum of the array it self is the maximum subarray sum since no negative element so 10.
For k = 1, S can be added at any 1 position so the maximum subarray sum becomes 12.
For k = 2, S can be added at any 2 positions so the maximum subarray sum becomes 14.
For k = 3, S can be added at any 3 positions so the maximum subarray sum becomes 16.
For k = 4, S can be added at any 4 positions so the maximum subarray sum becomes 18.Input: arr[] = {-1, -3, 5, 10}, S = 2
Output: 15 17 19 19 19
Approach: The approach is based on the prefix sum technique.
Initially the prefix sum of the array is calculated and using that,
- The maximum subarray sum of each sizes [1, N] is calculated and
- Then for each value of K, from [0, N], the value of S is added at K different positions and
- Maximum sum is printed as the output.
Follow these steps to solve the above problem:
- Initialize the array prefixsum[] to store the prefix sum of the array and the array msum[] to store the maximum of subarray sum of size i.
- Now iterate through the array and calculate the prefix sum of the array.
- Using two for loops calculate maximum subarray sum of each size i and store in msum[i].
- Now for each k from [0, n] add s at k distinct positions to maximize the subarray sum of size i.
- Print the maximum subarray sum for each k.
Below is the implementation of the above approach:
C++
// C++ program for largest sum // contiguous subarray by adding S // exactly at K different positions #include <bits/stdc++.h> using namespace std; // Function to find the largest sum // subarray after adding s at k // different positions for k from [0, n] void find_maxsum_subarray( int arr[], int n, int s) { int msum[n]; int prefix_sum[n + 1] = { 0 }; prefix_sum[0] = 0; // Find the prefix sum for ( int i = 0; i < n; i++) { if (i == 0) prefix_sum[i + 1] = arr[i]; else prefix_sum[i + 1] = arr[i] + prefix_sum[i]; } // For each subarray of size i // find the maximum sum for ( int i = 0; i < n; i++) { int mx_sum = INT_MIN; // Check for every subarray of size i for ( int j = 0; j < n - i; j++) { mx_sum = max(mx_sum, prefix_sum[j + i + 1] - prefix_sum[j]); } // Store the maximum sub array sum for // each subarray of size i in msum array msum[i] = mx_sum; } // For every k check the max sum // subarray by adding s // at k different positions for ( int k = 0; k <= n; k++) { int mx_sum = 0; // For each maxsum of subarray of size i // check by s at k positions // find the maximum sum // after adding s at k positions for ( int i = 0; i < n; i++) { mx_sum = max(mx_sum, msum[i] + min(i + 1, k) * s); } // For each k // print the maximum subarray sum cout << mx_sum << " " ; } } // Driver code int main() { int arr[] = { 4, 1, 3, 2 }; int n = sizeof (arr) / sizeof (arr[0]); int s = 2; find_maxsum_subarray(arr, n, s); } |
Java
// Java program for largest sum // contiguous subarray by adding S // exactly at K different positions import java.io.*; class GFG { // Function to find the largest sum // subarray after adding s at k // different positions for k from [0, n] static void find_maxsum_subarray( int []arr, int n, int s) { int []msum = new int [n]; int []prefix_sum = new int [n + 1 ]; for ( int i = 0 ; i < n + 1 ; i++) { prefix_sum[i] = 0 ; } prefix_sum[ 0 ] = 0 ; // Find the prefix sum for ( int i = 0 ; i < n; i++) { if (i == 0 ) prefix_sum[i + 1 ] = arr[i]; else prefix_sum[i + 1 ] = arr[i] + prefix_sum[i]; } // For each subarray of size i // find the maximum sum for ( int i = 0 ; i < n; i++) { int mx_sum = Integer.MIN_VALUE; // Check for every subarray of size i for ( int j = 0 ; j < n - i; j++) { mx_sum = Math.max(mx_sum, prefix_sum[j + i + 1 ] - prefix_sum[j]); } // Store the maximum sub array sum for // each subarray of size i in msum array msum[i] = mx_sum; } // For every k check the max sum // subarray by adding s // at k different positions for ( int k = 0 ; k <= n; k++) { int mx_sum = 0 ; // For each maxsum of subarray of size i // check by s at k positions // find the maximum sum // after adding s at k positions for ( int i = 0 ; i < n; i++) { mx_sum = Math.max(mx_sum, msum[i] + Math.min(i + 1 , k) * s); } // For each k // print the maximum subarray sum System.out.print(mx_sum + " " ); } } // Driver code public static void main (String[] args) { int []arr = { 4 , 1 , 3 , 2 }; int n = arr.length; int s = 2 ; find_maxsum_subarray(arr, n, s); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python3 program for largest sum # contiguous subarray by adding S # exactly at K different positions # Function to find the largest sum # subarray after adding s at k # different positions for k from [0, n] import sys def find_maxsum_subarray(arr, n, s): msum = [ 0 ] * n prefix_sum = [ 0 ] * (n + 1 ) # Find the prefix sum for i in range (n): if (i = = 0 ): prefix_sum[i + 1 ] = arr[i] else : prefix_sum[i + 1 ] = arr[i] + prefix_sum[i] # For each subarray of size i # find the maximum sum for i in range (n): mx_sum = - sys.maxsize - 1 # Check for every subarray of size i for j in range (n - i): mx_sum = max (mx_sum,prefix_sum[j + i + 1 ] - prefix_sum[j]) # Store the maximum sub array sum for # each subarray of size i in msum array msum[i] = mx_sum # For every k check the max sum # subarray by adding s # at k different positions for k in range (n + 1 ): mx_sum = 0 # For each maxsum of subarray of size i # check by s at k positions # find the maximum sum # after adding s at k positions for i in range (n): mx_sum = max (mx_sum,msum[i] + min (i + 1 , k) * s) # For each k # print the maximum subarray sum print (mx_sum,end = " " ) # Driver code arr = [ 4 , 1 , 3 , 2 ] n = len (arr) s = 2 find_maxsum_subarray(arr, n, s) # This code is contributed by shinjanpatra |
C#
// C# program for largest sum // contiguous subarray by adding S // exactly at K different positions using System; class GFG { // Function to find the largest sum // subarray after adding s at k // different positions for k from [0, n] static void find_maxsum_subarray( int []arr, int n, int s) { int []msum = new int [n]; int []prefix_sum = new int [n + 1]; for ( int i = 0; i < n + 1; i++) { prefix_sum[i] = 0; } prefix_sum[0] = 0; // Find the prefix sum for ( int i = 0; i < n; i++) { if (i == 0) prefix_sum[i + 1] = arr[i]; else prefix_sum[i + 1] = arr[i] + prefix_sum[i]; } // For each subarray of size i // find the maximum sum for ( int i = 0; i < n; i++) { int mx_sum = Int32.MinValue; // Check for every subarray of size i for ( int j = 0; j < n - i; j++) { mx_sum = Math.Max(mx_sum, prefix_sum[j + i + 1] - prefix_sum[j]); } // Store the maximum sub array sum for // each subarray of size i in msum array msum[i] = mx_sum; } // For every k check the max sum // subarray by adding s // at k different positions for ( int k = 0; k <= n; k++) { int mx_sum = 0; // For each maxsum of subarray of size i // check by s at k positions // find the maximum sum // after adding s at k positions for ( int i = 0; i < n; i++) { mx_sum = Math.Max(mx_sum, msum[i] + Math.Min(i + 1, k) * s); } // For each k // print the maximum subarray sum Console.Write(mx_sum + " " ); } } // Driver code public static void Main() { int []arr = { 4, 1, 3, 2 }; int n = arr.Length; int s = 2; find_maxsum_subarray(arr, n, s); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for largest sum // contiguous subarray by adding S // exactly at K different positions const INT_MIN = -2147483647 - 1; // Function to find the largest sum // subarray after adding s at k // different positions for k from [0, n] const find_maxsum_subarray = (arr, n, s) => { let msum = new Array(n).fill(0); let prefix_sum = new Array(n + 1).fill(0); prefix_sum[0] = 0; // Find the prefix sum for (let i = 0; i < n; i++) { if (i == 0) prefix_sum[i + 1] = arr[i]; else prefix_sum[i + 1] = arr[i] + prefix_sum[i]; } // For each subarray of size i // find the maximum sum for (let i = 0; i < n; i++) { let mx_sum = INT_MIN; // Check for every subarray of size i for (let j = 0; j < n - i; j++) { mx_sum = Math.max(mx_sum, prefix_sum[j + i + 1] - prefix_sum[j]); } // Store the maximum sub array sum for // each subarray of size i in msum array msum[i] = mx_sum; } // For every k check the max sum // subarray by adding s // at k different positions for (let k = 0; k <= n; k++) { let mx_sum = 0; // For each maxsum of subarray of size i // check by s at k positions // find the maximum sum // after adding s at k positions for (let i = 0; i < n; i++) { mx_sum = Math.max(mx_sum, msum[i] + Math.min(i + 1, k) * s); } // For each k // print the maximum subarray sum document.write(`${mx_sum} `); } } // Driver code let arr = [4, 1, 3, 2]; let n = arr.length; let s = 2; find_maxsum_subarray(arr, n, s); // This code is contributed by rakeshsahni </script> |
10 12 14 16 18
Time Complexity: O(N^2) where N is the size of the array.
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!