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