Sum of maximum of all subarrays | Divide and Conquer | JavaScript 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 ; input array ; Size of array ; Builind the segment - tree
class pair { constructor ( first , second ) { this . first = first ; this . second = second ; } } let seg_max = 51 ; let seg_tree = new Array ( seg_max ) ; let n ; function buildMaxTree ( l , r , i , arr ) { if ( l == r ) { seg_tree [ i ] = new pair ( arr [ l ] , l ) ; return seg_tree [ i ] ; } seg_tree [ i ] = max ( buildMaxTree ( l , Math . floor ( ( l + r ) / 2 ) , 2 * i + 1 , arr ) , buildMaxTree ( Math . floor ( ( l + r ) / 2 ) + 1 , r , 2 * i + 2 , arr ) ) ; return seg_tree [ i ] ; } function rangeMax ( l , r , arr , i , sl , sr ) { if ( sr < l sl > r ) return new pair ( Number . MIN_VALUE , - 1 ) ; if ( sl >= l && sr <= r ) return seg_tree [ i ] ; return max ( rangeMax ( l , r , arr , 2 * i + 1 , sl , Math . floor ( ( sl + sr ) / 2 ) ) , rangeMax ( l , r , arr , 2 * i + 2 , Math . floor ( ( sl + sr ) / 2 ) + 1 , sr ) ) ; } function max ( f , s ) { if ( f . first > s . first ) return f ; else return s ; } function maxSumSubarray ( arr , l , r ) { if ( l > r ) return 0 ; let 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 ) ; } let arr = [ 1 , 3 , 1 , 7 ] ; n = arr . length ; buildMaxTree ( 0 , n - 1 , 0 , arr ) ; document . write ( maxSumSubarray ( arr , 0 , n - 1 ) ) ;