Maximize Sum possible by subtracting same value from all elements of a Subarray of the given Array | Function to find the maximum sum by subtracting same value from all elements of a Subarray ; Stores previous smaller element ; Stores next smaller element ; Calculate contribution of each element ; Return answer ; Function to generate previous smaller element for each array element ; The first element has no previous smaller ; Stack to keep track of elements that have occurred previously ; Push the first index ; Pop all the elements until the previous element is smaller than current element ; Store the previous smaller element ; Push the index of the current element ; Return the array ; Function to generate next smaller element for each array element ; Stack to keep track of elements that have occurring next ; Iterate in reverse order for calculating next smaller ; Pop all the elements until the next element is smaller than current element ; Store the next smaller element ; Push the index of the current element ; Return the array ; Driver code
def findMaximumSum ( a , n ) : NEW_LINE INDENT prev_smaller = findPrevious ( a , n ) NEW_LINE next_smaller = findNext ( a , n ) NEW_LINE max_value = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT max_value = max ( max_value , a [ i ] * ( next_smaller [ i ] - prev_smaller [ i ] - 1 ) ) NEW_LINE DEDENT return max_value NEW_LINE DEDENT def findPrevious ( a , n ) : NEW_LINE INDENT ps = [ 0 ] * n NEW_LINE ps [ 0 ] = - 1 NEW_LINE stack = [ ] NEW_LINE stack . append ( 0 ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT while len ( stack ) > 0 and a [ stack [ - 1 ] ] >= a [ i ] : NEW_LINE INDENT stack . pop ( ) NEW_LINE DEDENT ps [ i ] = stack [ - 1 ] if len ( stack ) > 0 else - 1 NEW_LINE stack . append ( i ) NEW_LINE DEDENT return ps NEW_LINE DEDENT def findNext ( a , n ) : NEW_LINE INDENT ns = [ 0 ] * n NEW_LINE ns [ n - 1 ] = n NEW_LINE stack = [ ] NEW_LINE stack . append ( n - 1 ) NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT while ( len ( stack ) > 0 and a [ stack [ - 1 ] ] >= a [ i ] ) : NEW_LINE INDENT stack . pop ( ) NEW_LINE DEDENT ns [ i ] = stack [ - 1 ] if len ( stack ) > 0 else n NEW_LINE stack . append ( i ) NEW_LINE DEDENT return ns NEW_LINE DEDENT n = 3 NEW_LINE a = [ 80 , 48 , 82 ] NEW_LINE print ( findMaximumSum ( a , n ) ) NEW_LINE