Maximum sum subarray of size range [L, R]

0 0 6 minutes read

Given an integer array arr[] of size N and two integer L and R. The task is to find the maximum sum subarray of size between L and R (both inclusive).
Example:

Input: arr[] = {1, 2, 2, 1}, L = 1, R = 3
Output: 5
Explanation:
Subarray of size 1 are {1}, {2}, {2}, {1} and maximum sum subarray = 2 for subarray {2}.
Subarray of size 2 are {1, 2}, {2, 2}, {2, 1}, and maximum sum subarray = 4 for subarray {2, 2}.
Subarray of size 3 are {1, 2, 2}, {2, 2, 1}, and maximum sum subarray = 5 for subarray {2, 2, 1}.
Hence the maximum possible sum subarray is 5.
Input: arr[] = {-1, -3, -7, -11}, L = 1, R = 4
Output: -1

Approach:

Here we will use the concept of sliding window which is discuss in this post.
First calculate prefix sum of array in array pre[].
Next iterate over the range L to N -1, and consider all subarray of size L to R.
Create a multiset for storing prefix sums of subarray length L to R.
Now to find maximum sum subarray ending at index i just subtract pre[i] and minimum of all values from pre[i – L] to pre[i – R].
Finally return maximum of all sums.

Here is the implementation of the above approach:

C++

// C++ program to find Maximum sum
// subarray of size between L and R.
 
#include <bits/stdc++.h>
using namespace std;
 
// function to find Maximum sum subarray
// of size between L and R
void max_sum_subarray(vector<int> arr,
                      int L, int R)
{
    int n = arr.size();
    int pre[n] = { 0 };
 
    // calculating prefix sum
    pre[0] = arr[0];
    for (int i = 1; i < n; i++) {
        pre[i] = pre[i - 1] + arr[i];
    }
    multiset<int> s1;
 
    // maintain 0 for initial
    // values of i upto R
    // Once i = R, then
    // we need to erase that 0 from
    // our multiset as our first
    // index of subarray
    // cannot be 0 anymore.
    s1.insert(0);
    int ans = INT_MIN;
 
    ans = max(ans, pre[L - 1]);
 
    // we maintain flag to
    // counter if that initial
    // 0 was erased from set or not.
    int flag = 0;
 
    for (int i = L; i < n; i++) {
 
        // erase 0 from multiset once i=b
        if (i - R >= 0) {
            if (flag == 0) {
 
                auto it = s1.find(0);
                s1.erase(it);
                flag = 1;
            }
        }
        // insert pre[i-L]
        if (i - L >= 0)
            s1.insert(pre[i - L]);
 
        // find minimum value in multiset.
        ans = max(ans,
                  pre[i] - *s1.begin());
 
        // erase pre[i-R]
        if (i - R >= 0) {
            auto it = s1.find(pre[i - R]);
            s1.erase(it);
        }
    }
    cout << ans << endl;
}
 
// Driver code
int main()
{
    int L, R;
    L = 1;
    R = 3;
    vector<int> arr = { 1, 2, 2, 1 };
    max_sum_subarray(arr, L, R);
    return 0;
}

Java

// Java program to find Maximum sum 
// subarray of size between L and R. 
import java.util.*;
class GFG {
// function to find Maximum sum subarray
// of size between L and R
static void max_sum_subarray(List<Integer> arr, int L, int R){
     
    int n = arr.size();
    int[] pre = new int[n + 1];
 
    // calculating prefix sum
    // here pre[0] = 0
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1]+arr.get(i - 1);
    }    
     
      // treemap for storing prefix sums for 
      // subarray length L to R
    TreeMap<Integer, Integer> s1 = new TreeMap<>();
 
    int ans = Integer.MIN_VALUE;
 
    for (int i = L; i <= n; i++) {
         
        // if i > R, erase pre[i - R - 1]
        // note that pre[0] = 0
        if (i > R) { 
            // decrement count of pre[i - R - 1]
            s1.put(pre[i - R - 1], s1.get(pre[i - R - 1])-1); 
            // if count is zero, element is not present
            // in map so remove it
            if (s1.get(pre[i - R - 1]) == 0) 
                s1.remove(pre[i - R - 1]);
        }
 
        // insert pre[i - L]
        s1.put(pre[i - L], s1.getOrDefault(pre[i - L], 0)+1);
 
        // find minimum value in treemap.
        ans = Math.max(ans, pre[i] - s1.firstKey());
 
    }
    System.out.println(ans);
}
 
// Driver code
    public static void main(String[] args){
        int L, R;
        L = 1;
        R = 3;
        List<Integer> arr = Arrays.asList(1, 2, 2, 1);
        max_sum_subarray(arr, L, R);
    }
}
 
// This code is contributed by Utkarsh Sharma

Python3

# Python3 program to find maximum sum
# subarray of size between L and R.
import sys
 
# Function to find maximum sum subarray
# of size between L and R
def max_sum_subarray(arr, L, R):
 
    n = len(arr)
    pre = n * [0]
 
    # Calculating prefix sum
    pre[0] = arr[0]
    for i in range(1, n):
        pre[i] = pre[i - 1] + arr[i]
 
    s1 = []
 
    # Maintain 0 for initial
    # values of i upto R
    # Once i = R, then
    # we need to erase that 0 from
    # our multiset as our first
    # index of subarray
    # cannot be 0 anymore.
    s1.append(0)
    ans = -sys.maxsize - 1
 
    ans = max(ans, pre[L - 1])
 
    # We maintain flag to
    # counter if that initial
    # 0 was erased from set or not.
    flag = 0
 
    for i in range(L, n):
         
        # Erase 0 from multiset once i=b
        if (i - R >= 0):
            if (flag == 0):
                s1.remove(0)
                flag = 1
     
        # Insert pre[i-L]
        if (i - L >= 0):
            s1.append(pre[i - L])
 
        # Find minimum value in multiset.
        ans = max(ans, pre[i] - s1[0])
 
        # Erase pre[i-R]
        if (i - R >= 0):
            s1.remove(pre[i - R])
 
    print(ans)
 
# Driver code
if __name__ == "__main__":
 
    L = 1
    R = 3
    arr = [ 1, 2, 2, 1 ]
     
    max_sum_subarray(arr, L, R)
 
# This code is contributed by chitranayal

C#

// C# program to find Maximum sum 
// subarray of size between L and R. 
using System;
using System.Collections.Generic;
class GFG 
{
     
    // function to find Maximum sum subarray 
    // of size between L and R 
    static void max_sum_subarray(List<int> arr, int L, int R) 
    { 
        int n = arr.Count; 
        int[] pre = new int[n];
       
        // calculating prefix sum 
        pre[0] = arr[0]; 
        for (int i = 1; i < n; i++) 
        { 
            pre[i] = pre[i - 1] + arr[i]; 
        } 
        List<int> s1 = new List<int>();
       
        // maintain 0 for initial 
        // values of i upto R 
        // Once i = R, then 
        // we need to erase that 0 from 
        // our multiset as our first 
        // index of subarray 
        // cannot be 0 anymore. 
        s1.Add(0); 
        int ans = Int32.MinValue; 
       
        ans = Math.Max(ans, pre[L - 1]); 
       
        // we maintain flag to 
        // counter if that initial 
        // 0 was erased from set or not. 
        int flag = 0; 
       
        for (int i = L; i < n; i++) 
        { 
       
            // erase 0 from multiset once i=b 
            if (i - R >= 0) 
            { 
                if (flag == 0)
                { 
       
                    int it = s1.IndexOf(0); 
                    s1.RemoveAt(it); 
                    flag = 1; 
                } 
            } 
            // insert pre[i-L] 
            if (i - L >= 0) 
                s1.Add(pre[i - L]); 
       
            // find minimum value in multiset. 
            ans = Math.Max(ans, pre[i] - s1[0]); 
       
            // erase pre[i-R] 
            if (i - R >= 0) 
            { 
                int it = s1.IndexOf(pre[i - R]); 
                s1.RemoveAt(it); 
            } 
        } 
        Console.WriteLine(ans); 
    }  
 
  // Driver code
  static void Main()
  {
    int L, R; 
    L = 1; 
    R = 3; 
    List<int> arr = new List<int>(){1, 2, 2, 1};
    max_sum_subarray(arr, L, R); 
  }
}
 
// This code is contributed by divyesh072019

Javascript

<script>
 
// Javascript program to find Maximum sum
// subarray of size between L and R.
 
// function to find Maximum sum subarray
  // of size between L and R
function max_sum_subarray(arr,L,R)
{
    let n = arr.length;
    let pre = new Array(n);
  
    // calculating prefix sum
    pre[0] = arr[0];
    for (let i = 1; i < n; i++)
    {
      pre[i] = pre[i - 1] + arr[i];
    }
    let s1 = []
  
    // maintain 0 for initial
    // values of i upto R
    // Once i = R, then
    // we need to erase that 0 from
    // our multiset as our first
    // index of subarray
    // cannot be 0 anymore.
    s1.push(0);
    let ans = Number.MIN_VALUE;
  
    ans = Math.max(ans, pre[L - 1]);
  
    // we maintain flag to
    // counter if that initial
    // 0 was erased from set or not.
    let flag = 0;
  
    for (let i = L; i < n; i++)
    {
  
      // erase 0 from multiset once i=b
      if (i - R >= 0)
      {
        if (flag == 0)
        {
          let it = s1.indexOf(0);
          s1.splice(it,1);
          flag = 1;
        }
      }
  
      // insert pre[i-L]
      if (i - L >= 0)
        s1.push(pre[i - L]);
  
      // find minimum value in multiset.
      ans = Math.max(ans, pre[i] - s1[0]);
  
      // erase pre[i-R]
      if (i - R >= 0)
      {
        let it = s1.indexOf(pre[i - R]);
        s1.splice(it,1);
      }
    }
    document.write(ans);
}
 
// Driver code
let L, R;
L = 1;
R = 3;
let arr = [1, 2, 2, 1];
max_sum_subarray(arr, L, R); 
                 
// This code is contributed by avanitrachhadiya2155
</script>

Output:

Time Complexity: O (N * log 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 zambiatek!