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
function findMaximumSum ( a , n ) { var prev_smaller = findPrevious ( a , n ) ; var next_smaller = findNext ( a , n ) ; var max_value = 0 ; for ( var i = 0 ; i < n ; i ++ ) { max_value = Math . max ( max_value , a [ i ] * ( next_smaller [ i ] - prev_smaller [ i ] - 1 ) ) ; } return max_value ; } function findPrevious ( a , n ) { var ps = Array ( n ) . fill ( 0 ) ; ps [ 0 ] = - 1 ; let stack = Array ( ) ; stack . push ( 0 ) ; for ( var i = 1 ; i < a . length ; i ++ ) { while ( stack . length > 0 && a [ stack [ stack . length - 1 ] ] >= a [ i ] ) stack . pop ( ) ; ps [ i ] = stack . length > 0 ? stack [ stack . length - 1 ] : - 1 ; stack . push ( i ) ; } return ps ; } function findNext ( a , n ) { var ns = Array ( n ) . fill ( 0 ) ; ns [ n - 1 ] = n ; var stack = Array ( ) ; stack . push ( n - 1 ) ; for ( var i = n - 2 ; i >= 0 ; i -- ) { while ( stack . length > 0 && a [ stack [ stack . length - 1 ] ] >= a [ i ] ) stack . pop ( ) ; ns [ i ] = stack . length > 0 ? stack [ stack . length - 1 ] : a . length ; stack . push ( i ) ; } return ns ; } var n = 3 ; var a = [ 80 , 48 , 82 ] ; document . write ( findMaximumSum ( a , n ) ) ;