Maximum sum subarray of size range [ L , R ] | Python3 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
import sys NEW_LINE def max_sum_subarray ( arr , L , R ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE pre = n * [ 0 ] NEW_LINE pre [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT pre [ i ] = pre [ i - 1 ] + arr [ i ] NEW_LINE DEDENT s1 = [ ] NEW_LINE s1 . append ( 0 ) NEW_LINE ans = - sys . maxsize - 1 NEW_LINE ans = max ( ans , pre [ L - 1 ] ) NEW_LINE flag = 0 NEW_LINE for i in range ( L , n ) : NEW_LINE INDENT if ( i - R >= 0 ) : NEW_LINE INDENT if ( flag == 0 ) : NEW_LINE INDENT s1 . remove ( 0 ) NEW_LINE flag = 1 NEW_LINE DEDENT DEDENT if ( i - L >= 0 ) : NEW_LINE INDENT s1 . append ( pre [ i - L ] ) NEW_LINE DEDENT ans = max ( ans , pre [ i ] - s1 [ 0 ] ) NEW_LINE if ( i - R >= 0 ) : NEW_LINE INDENT s1 . remove ( pre [ i - R ] ) NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT L = 1 NEW_LINE R = 3 NEW_LINE arr = [ 1 , 2 , 2 , 1 ] NEW_LINE max_sum_subarray ( arr , L , R ) NEW_LINE DEDENT