Monday, November 18, 2024
Google search engine
HomeData Modelling & AILargest sum contiguous subarray by adding S exactly at K different positions

Largest sum contiguous subarray by adding S exactly at K different positions

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>


 
 

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!

RELATED ARTICLES

Most Popular

Recent Comments