Sum of maximum of all subarrays | Divide and Conquer
Given an array arr[] of length N, the task is to find the sum of the maximum elements of every possible sub-array of the array.
Examples:
Input : arr[] = {1, 3, 1, 7} Output : 42 Max of all sub-arrays: {1} - 1 {1, 3} - 3 {1, 3, 1} - 3 {1, 3, 1, 7} - 7 {3} - 3 {3, 1} - 3 {3, 1, 7} - 7 {1} - 1 {1, 7} - 7 {7} - 7 1 + 3 + 3 + 7 + 3 + 3 + 7 + 1 + 7 + 7 = 42 Input : arr[] = {1, 1, 1, 1, 1} Output : 15
We have already discussed an O(N) approach using stack for this problem in this article.
Approach :
In this article, we will learn how to solve this problem using divide and conquer.
Let’s assume that element at ith index is largest of all. For any sub-array that contains index ‘i’, the element at ‘i’ will always be maximum in the sub-array.
If element at ith index is largest, we can safely say, that element ith index will be largest in (i+1)*(N-i) subarrays. So, its total contribution will be arr[i]*(i+1)*(N-i). Now, we will divide the array in two parts, (0, i-1) and (i+1, N-1) and apply the same algorithms to both of them separately.
So our general recurrence relation will be:
maxSumSubarray(arr, l, r) = arr[i]*(r-i+1)*(i-l+1) + maxSumSubarray(arr, l, i-1) + maxSumSubarray(arr, i+1, r) where i is index of maximum element in range [l, r].
Now, we need a way to efficiently answer rangeMax() queries. Segment tree will be an efficient way to answer this query. We will need to answer this query at most N times. Thus, the time complexity of our divide and conquer algorithm will O(Nlog(N)).
If we have to answer the problem “Sum of minimum of all subarrays” then we will use the segment tree to answer rangeMin() queries. For this, you can go through the article segment tree range minimum.
Below is the implementation code:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> #define seg_max 51 using namespace std; // Array to store segment tree. // In first we will store the maximum // of a range // In second, we will store index of // that range pair< int , int > seg_tree[seg_max]; // Size of array declared global // to maintain simplicity in code int n; // Function to build segment tree pair< int , int > buildMaxTree( int l, int r, int i, int arr[]) { // Base case if (l == r) { seg_tree[i] = { arr[l], l }; return seg_tree[i]; } // Finding the maximum among left and right child seg_tree[i] = max(buildMaxTree(l, (l + r) / 2, 2 * i + 1, arr), buildMaxTree((l + r) / 2 + 1, r, 2 * i + 2, arr)); // Returning the maximum to parent return seg_tree[i]; } // Function to perform range-max query in segment tree pair< int , int > rangeMax( int l, int r, int arr[], int i = 0, int sl = 0, int sr = n - 1) { // Base cases if (sr < l || sl > r) return { INT_MIN, -1 }; if (sl >= l and sr <= r) return seg_tree[i]; // Finding the maximum among left and right child 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)); } // Function to find maximum sum subarray int maxSumSubarray( int arr[], int l = 0, int r = n - 1) { // base case if (l > r) return 0; // range-max query to determine // largest in the range. pair< int , int > a = rangeMax(l, r, arr); // divide the array in two parts return a.first * (r - a.second + 1) * (a.second - l + 1) + maxSumSubarray(arr, l, a.second - 1) + maxSumSubarray(arr, a.second + 1, r); } // Driver Code int main() { // Input array int arr[] = { 1, 3, 1, 7 }; // Size of array n = sizeof (arr) / sizeof ( int ); // Builind the segment-tree buildMaxTree(0, n - 1, 0, arr); cout << maxSumSubarray(arr); return 0; } |
Java
// Java implementation of the above approach 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 ; // Array to store segment tree. // In first we will store the maximum // of a range // In second, we will store index of // that range static pair[] seg_tree = new pair[seg_max]; // Size of array declared global // to maintain simplicity in code static int n; // Function to build segment tree static pair buildMaxTree( int l, int r, int i, int arr[]) { // Base case if (l == r) { seg_tree[i] = new pair(arr[l], l); return seg_tree[i]; } // Finding the maximum among left and right child seg_tree[i] = max(buildMaxTree(l, (l + r) / 2 , 2 * i + 1 , arr), buildMaxTree((l + r) / 2 + 1 , r, 2 * i + 2 , arr)); // Returning the maximum to parent return seg_tree[i]; } // Function to perform range-max query in segment tree static pair rangeMax( int l, int r, int arr[], int i, int sl, int sr) { // Base cases if (sr < l || sl > r) return new pair(Integer.MIN_VALUE, - 1 ); if (sl >= l && sr <= r) return seg_tree[i]; // Finding the maximum among left and right child 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; } // Function to find maximum sum subarray static int maxSumSubarray( int arr[], int l, int r) { // base case if (l > r) return 0 ; // range-max query to determine // largest in the range. pair a = rangeMax(l, r, arr, 0 , 0 , n - 1 ); // divide the array in two parts return a.first * (r - a.second + 1 ) * (a.second - l + 1 ) + maxSumSubarray(arr, l, a.second - 1 ) + maxSumSubarray(arr, a.second + 1 , r); } // Driver Code public static void main(String[] args) { // Input array int arr[] = { 1 , 3 , 1 , 7 }; // Size of array n = arr.length; // Builind the segment-tree buildMaxTree( 0 , n - 1 , 0 , arr); System.out.print(maxSumSubarray(arr, 0 , n - 1 )); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the above approach import sys seg_max = 51 # Array to store segment tree. # In first we will store the maximum # of a range # In second, we will store index of # that range seg_tree = [[] for i in range (seg_max)] # Function to build segment tree def buildMaxTree(l, r, i, arr): global n, seg_tree, seg_max # Base case if l = = r: seg_tree[i] = [arr[l], l] return seg_tree[i] # Finding the maximum among left and right child seg_tree[i] = max (buildMaxTree(l, int ((l + r) / 2 ), 2 * i + 1 , arr), buildMaxTree( int ((l + r) / 2 ) + 1 , r, 2 * i + 2 , arr)) # Returning the maximum to parent return seg_tree[i] # Function to perform range-max query in segment tree def rangeMax(l, r, arr, i, sl, sr): global n, seg_tree, seg_max # Base cases if sr < l or sl > r: return [ - sys.maxsize, - 1 ] if sl > = l and sr < = r: return seg_tree[i] # Finding the maximum among left and right child return max (rangeMax(l, r, arr, 2 * i + 1 , sl, int ((sl + sr) / 2 )), rangeMax(l, r, arr, 2 * i + 2 , int ((sl + sr) / 2 ) + 1 , sr)) def Max (f, s): if f[ 0 ] > s[ 0 ]: return f else : return s # Function to find maximum sum subarray def maxSumSubarray(arr, l, r): # base case if l > r: return 0 # range-max query to determine # largest in the range. a = rangeMax(l, r, arr, 0 , 0 , n - 1 ) # divide the array in two parts return a[ 0 ] * (r - a[ 1 ] + 1 ) * (a[ 1 ] - l + 1 ) + maxSumSubarray(arr, l, a[ 1 ] - 1 ) + maxSumSubarray(arr, a[ 1 ] + 1 , r) # Input array arr = [ 1 , 3 , 1 , 7 ] # Size of array n = len (arr) # Builind the segment-tree buildMaxTree( 0 , n - 1 , 0 , arr) print (maxSumSubarray(arr, 0 , n - 1 )) # This code is contributed by decode2207. |
C#
// C# implementation of the above approach using System; class GFG { class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } static readonly int seg_max = 51; // Array to store segment tree. // In first we will store the maximum // of a range // In second, we will store index of // that range static pair[] seg_tree = new pair[seg_max]; // Size of array declared global // to maintain simplicity in code static int n; // Function to build segment tree static pair buildMaxTree( int l, int r, int i, int []arr) { // Base case if (l == r) { seg_tree[i] = new pair(arr[l], l); return seg_tree[i]; } // Finding the maximum among left and right child seg_tree[i] = max(buildMaxTree(l, (l + r) / 2, 2 * i + 1, arr), buildMaxTree((l + r) / 2 + 1, r, 2 * i + 2, arr)); // Returning the maximum to parent return seg_tree[i]; } // Function to perform range-max query in segment tree static pair rangeMax( int l, int r, int []arr, int i, int sl, int sr) { // Base cases if (sr < l || sl > r) return new pair( int .MinValue, -1); if (sl >= l && sr <= r) return seg_tree[i]; // Finding the maximum among left and right child 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; } // Function to find maximum sum subarray static int maxSumSubarray( int []arr, int l, int r) { // base case if (l > r) return 0; // range-max query to determine // largest in the range. pair a = rangeMax(l, r, arr, 0, 0, n - 1); // divide the array in two parts return a.first * (r - a.second + 1) * (a.second - l + 1) + maxSumSubarray(arr, l, a.second - 1) + maxSumSubarray(arr, a.second + 1, r); } // Driver Code public static void Main(String[] args) { // Input array int []arr = { 1, 3, 1, 7 }; // Size of array n = arr.Length; // Builind the segment-tree buildMaxTree(0, n - 1, 0, arr); Console.Write(maxSumSubarray(arr, 0, n - 1)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation of the above approach class pair { constructor(first,second) { this .first = first; this .second = second; } } let seg_max = 51; // Array to store segment tree. // In first we will store the maximum // of a range // In second, we will store index of // that range let seg_tree = new Array(seg_max); // Size of array declared global // to maintain simplicity in code let n; // Function to build segment tree function buildMaxTree(l,r,i,arr) { // Base case if (l == r) { seg_tree[i] = new pair(arr[l], l); return seg_tree[i]; } // Finding the maximum among left and right child 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)); // Returning the maximum to parent return seg_tree[i]; } // Function to perform range-max query in segment tree function rangeMax(l,r,arr,i,sl,sr) { // Base cases if (sr < l || sl > r) return new pair(Number.MIN_VALUE, -1); if (sl >= l && sr <= r) return seg_tree[i]; // Finding the maximum among left and right child 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 to find maximum sum subarray function maxSumSubarray(arr,l,r) { // base case if (l > r) return 0; // range-max query to determine // largest in the range. let a = rangeMax(l, r, arr, 0, 0, n - 1); // divide the array in two parts return a.first * (r - a.second + 1) * (a.second - l + 1) + maxSumSubarray(arr, l, a.second - 1) + maxSumSubarray(arr, a.second + 1, r); } // Driver Code // Input array let arr = [ 1, 3, 1, 7 ]; // Size of array n = arr.length; // Builind the segment-tree buildMaxTree(0, n - 1, 0, arr); document.write(maxSumSubarray(arr, 0, n - 1)); // This code is contributed by rag2127 </script> |
42
Time complexity : O(Nlog(N))
Contact Us