text: Maximize Sum possible by subtracting same value from all elements of a Subarray of the given Array | C ++ program to implement the above approach ; 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 ; 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 ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > findPrevious ( vector < int > a , int n ) { vector < int > ps ( n ) ; ps [ 0 ] = -1 ; stack < int > Stack ; Stack . push ( 0 ) ; for ( int i = 1 ; i < n ; i ++ ) { while ( Stack . size ( ) > 0 && a [ Stack . top ( ) ] >= a [ i ] ) Stack . pop ( ) ; ps [ i ] = Stack . size ( ) > 0 ? Stack . top ( ) : -1 ; Stack . push ( i ) ; } return ps ; } vector < int > findNext ( vector < int > a , int n ) { vector < int > ns ( n ) ; ns [ n - 1 ] = n ; stack < int > Stack ; Stack . push ( n - 1 ) ; for ( int i = n - 2 ; i >= 0 ; i -- ) { while ( Stack . size ( ) > 0 && a [ Stack . top ( ) ] >= a [ i ] ) Stack . pop ( ) ; ns [ i ] = Stack . size ( ) > 0 ? Stack . top ( ) : n ; Stack . push ( i ) ; } return ns ; } int findMaximumSum ( vector < int > a , int n ) { vector < int > prev_smaller = findPrevious ( a , n ) ; vector < int > next_smaller = findNext ( a , n ) ; int max_value = 0 ; for ( int i = 0 ; i < n ; i ++ ) { max_value = max ( max_value , a [ i ] * ( next_smaller [ i ] - prev_smaller [ i ] - 1 ) ) ; } return max_value ; } int main ( ) { int n = 3 ; vector < int > a { 80 , 48 , 82 } ; cout << findMaximumSum ( a , n ) ; return 0 ; }