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 codeint 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 positionsimport 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 sysdef 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 codearr = [ 4, 1, 3, 2 ]n = len(arr)s = 2find_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 positionsusing 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> |
Output
10 12 14 16 18
Time Complexity: O(N^2) where N is the size of the array.
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!
