Sum of maximum of all subarrays | Divide and Conquer | C ++ 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
#include <bits/stdc++.h> NEW_LINE #define seg_max  51 NEW_LINE using namespace std ; pair < int , int > seg_tree [ seg_max ] ; int n ; pair < int , int > buildMaxTree ( int l , int r , int i , int arr [ ] ) { if ( l == r ) { seg_tree [ i ] = { 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 ] ; } pair < int , int > rangeMax ( int l , int r , int arr [ ] , int i = 0 , int sl = 0 , int sr = n - 1 ) { if ( sr < l sl > r ) return { INT_MIN , -1 } ; if ( sl >= l and 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 ) ) ; } int maxSumSubarray ( int arr [ ] , int l = 0 , int r = n - 1 ) { if ( l > r ) return 0 ; pair < int , int > a = rangeMax ( l , r , arr ) ; return a . first * ( r - a . second + 1 ) * ( a . second - l + 1 ) + maxSumSubarray ( arr , l , a . second - 1 ) + maxSumSubarray ( arr , a . second + 1 , r ) ; } int main ( ) { int arr [ ] = { 1 , 3 , 1 , 7 } ; n = sizeof ( arr ) / sizeof ( int ) ; buildMaxTree ( 0 , n - 1 , 0 , arr ) ; cout << maxSumSubarray ( arr ) ; return 0 ; }