Maximize Sum possible by subtracting same value from all elements of a Subarray of the given Array | Java Program to implement the above approach ; 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
import java . util . * ; public class GFG { public static int findMaximumSum ( int [ ] a , int n ) { int prev_smaller [ ] = findPrevious ( a , n ) ; int next_smaller [ ] = findNext ( a , n ) ; int max_value = 0 ; for ( int i = 0 ; i < n ; i ++ ) { max_value = Math . max ( max_value , a [ i ] * ( next_smaller [ i ] - prev_smaller [ i ] - 1 ) ) ; } return max_value ; } public static int [ ] findPrevious ( int [ ] a , int n ) { int ps [ ] = new int [ n ] ; ps [ 0 ] = - 1 ; Stack < Integer > stack = new Stack < > ( ) ; stack . push ( 0 ) ; for ( int i = 1 ; i < a . length ; i ++ ) { while ( stack . size ( ) > 0 && a [ stack . peek ( ) ] >= a [ i ] ) stack . pop ( ) ; ps [ i ] = stack . size ( ) > 0 ? stack . peek ( ) : - 1 ; stack . push ( i ) ; } return ps ; } public static int [ ] findNext ( int [ ] a , int n ) { int ns [ ] = new int [ n ] ; ns [ n - 1 ] = n ; Stack < Integer > stack = new Stack < > ( ) ; stack . push ( n - 1 ) ; for ( int i = n - 2 ; i >= 0 ; i -- ) { while ( stack . size ( ) > 0 && a [ stack . peek ( ) ] >= a [ i ] ) stack . pop ( ) ; ns [ i ] = stack . size ( ) > 0 ? stack . peek ( ) : a . length ; stack . push ( i ) ; } return ns ; } public static void main ( String args [ ] ) { int n = 3 ; int a [ ] = { 80 , 48 , 82 } ; System . out . println ( findMaximumSum ( a , n ) ) ; } }