Sum of maximum of all subarrays | Divide and Conquer | Java implementation of the above approach ; Array to store segment tree . In first we will store the maximum of a range In second , we will store index of that range ; Size of array declared global to maintain simplicity in code ; Function to build segment tree ; Base case ; Finding the maximum among left and right child ; Returning the maximum to parent ; Function to perform range - max query in segment tree ; Base cases ; Finding the maximum among left and right child ; Function to find maximum sum subarray ; base case ; range - max query to determine largest in the range . ; divide the array in two parts ; Driver Code ; Input array ; Size of array ; Builind the segment - tree
class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static final int seg_max = 51 ; static pair [ ] seg_tree = new pair [ seg_max ] ; static int n ; static pair buildMaxTree ( int l , int r , int i , int arr [ ] ) { if ( l == r ) { seg_tree [ i ] = new pair ( arr [ l ] , l ) ; return seg_tree [ i ] ; } seg_tree [ i ] = max ( buildMaxTree ( l , ( l + r ) / 2 , 2 * i + 1 , arr ) , buildMaxTree ( ( l + r ) / 2 + 1 , r , 2 * i + 2 , arr ) ) ; return seg_tree [ i ] ; } static pair rangeMax ( int l , int r , int arr [ ] , int i , int sl , int sr ) { if ( sr < l sl > r ) return new pair ( Integer . MIN_VALUE , - 1 ) ; if ( sl >= l && sr <= r ) return seg_tree [ i ] ; return max ( rangeMax ( l , r , arr , 2 * i + 1 , sl , ( sl + sr ) / 2 ) , rangeMax ( l , r , arr , 2 * i + 2 , ( sl + sr ) / 2 + 1 , sr ) ) ; } static pair max ( pair f , pair s ) { if ( f . first > s . first ) return f ; else return s ; } static int maxSumSubarray ( int arr [ ] , int l , int r ) { if ( l > r ) return 0 ; pair a = rangeMax ( l , r , arr , 0 , 0 , n - 1 ) ; return a . first * ( r - a . second + 1 ) * ( a . second - l + 1 ) + maxSumSubarray ( arr , l , a . second - 1 ) + maxSumSubarray ( arr , a . second + 1 , r ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 3 , 1 , 7 } ; n = arr . length ; buildMaxTree ( 0 , n - 1 , 0 , arr ) ; System . out . print ( maxSumSubarray ( arr , 0 , n - 1 ) ) ; } }