human
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"
Solution in Python:
assistant
#Here is code to maximize Sum possible by subtracting same value from all elements of a Subarray of the given Array and the other steps required.
 def findMaximumSum ( a , n ) :
	prev_smaller = findPrevious ( a , n )
	next_smaller = findNext ( a , n )
	max_value = 0
	for i in range ( n ) :
		max_value = max ( max_value , a [ i ] * ( next_smaller [ i ] - prev_smaller [ i ] - 1 ) )
	return max_value
def findPrevious ( a , n ) :
	ps = [ 0 ] * n
	ps [ 0 ] = - 1
	stack = [ ]
	stack . append ( 0 )
	for i in range ( 1 , n ) :
		while len ( stack ) > 0 and a [ stack [ - 1 ] ] >= a [ i ] :
			stack . pop ( )
		ps [ i ] = stack [ - 1 ] if len ( stack ) > 0 else - 1
		stack . append ( i )
	return ps
def findNext ( a , n ) :
	ns = [ 0 ] * n
	ns [ n - 1 ] = n
	stack = [ ]
	stack . append ( n - 1 )
	for i in range ( n - 2 , - 1 , - 1 ) :
		while ( len ( stack ) > 0 and a [ stack [ - 1 ] ] >= a [ i ] ) :
			stack . pop ( )
		ns [ i ] = stack [ - 1 ] if len ( stack ) > 0 else n
		stack . append ( i )
	return ns
n = 3
a = [ 80 , 48 , 82 ]
print ( findMaximumSum ( a , n ) )