Queries to find maximum sum contiguous subarrays of given length in a rotating array | Function to calculate the maximum sum of length k ; Calculating the max sum for the first k elements ; Find subarray with maximum sum ; Update the sum ; Return maximum sum ; Function to calculate gcd of the two numbers n1 and n2 ; Base Case ; Recursively find the GCD ; Function to rotate the array by Y ; For handling k >= N ; Dividing the array into number of sets ; Rotate the array by Y ; Update arr [ j ] ; Return the rotated array ; Function that performs the queries on the given array ; Traverse each query ; If query of type X = 1 ; Print the array ; If query of type X = 2 ; Driver Code ; Given array arr [ ] ; Given Queries ; Function call
def MaxSum ( arr , n , k ) : NEW_LINE INDENT i , max_sum = 0 , 0 NEW_LINE sum = 0 NEW_LINE while i < k : NEW_LINE INDENT sum += arr [ i ] NEW_LINE i += 1 NEW_LINE DEDENT max_sum = sum NEW_LINE while ( i < n ) : NEW_LINE INDENT sum = sum - arr [ i - k ] + arr [ i ] NEW_LINE if ( max_sum < sum ) : NEW_LINE INDENT max_sum = sum NEW_LINE DEDENT i += 1 NEW_LINE DEDENT return max_sum NEW_LINE DEDENT def gcd ( n1 , n2 ) : NEW_LINE INDENT if ( n2 == 0 ) : NEW_LINE INDENT return n1 NEW_LINE DEDENT else : NEW_LINE INDENT return gcd ( n2 , n1 % n2 ) NEW_LINE DEDENT DEDENT def RotateArr ( arr , n , d ) : NEW_LINE INDENT i = 0 NEW_LINE j = 0 NEW_LINE d = d % n NEW_LINE no_of_sets = gcd ( d , n ) NEW_LINE for i in range ( no_of_sets ) : NEW_LINE INDENT temp = arr [ i ] NEW_LINE j = i NEW_LINE while ( True ) : NEW_LINE INDENT k = j + d NEW_LINE if ( k >= n ) : NEW_LINE INDENT k = k - n NEW_LINE DEDENT if ( k == i ) : NEW_LINE INDENT break NEW_LINE DEDENT arr [ j ] = arr [ k ] NEW_LINE j = k NEW_LINE DEDENT arr [ j ] = temp NEW_LINE DEDENT return arr NEW_LINE DEDENT def performQuery ( arr , Q , q ) : NEW_LINE INDENT N = len ( arr ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT if ( Q [ i ] [ 0 ] == 1 ) : NEW_LINE INDENT arr = RotateArr ( arr , N , Q [ i ] [ 1 ] ) NEW_LINE for t in arr : NEW_LINE INDENT print ( t , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( MaxSum ( arr , N , Q [ i ] [ 1 ] ) ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE q = 5 NEW_LINE Q = [ [ 1 , 2 ] , [ 2 , 3 ] , [ 1 , 3 ] , [ 1 , 1 ] , [ 2 , 4 ] ] NEW_LINE performQuery ( arr , Q , q ) NEW_LINE DEDENT