Sum of maximum of all subarrays | Divide and Conquer

There is an array arr[] of length N. Your task is to find the sum of the minimum elements of each possible sub-array of the array.

Examples:

 
Input : arr[] = {2, 4, 6, 8, 10}
Output : 75
Explanation :
Min of all sub-arrays:
{2} - 2
{2, 4} - 2
{2, 4, 6} - 2
{2, 4, 6, 8} - 2
{2, 4, 6, 8, 10} - 2
{4} - 4
{4, 6} - 4
{4, 6, 8} - 4
{4, 6, 8, 10} - 4
{6} - 6
{6, 8} - 6
{6, 8, 10} - 6
{8} - 8
{8, 10} - 8
{10} - 10

Now, sum all the minimum values of subarrays:
2 + 2 + 2 + 2 + 2 + 4 + 4 + 4 + 4 + 6 + 6 + 6 + 8 + 8 + 10 = 75
So, the output is 75.


Input : arr[] = {3, 5, 2, 7, 4}
Output : 41

We can solve this problem using O(N) approach using stack. In this article, we will learn how to solve this problem using divide and conquer. Let us assume that the element at ith index is the smallest among all. For any sub-array that has index ‘i’, the element at ‘i’ in the sub-array will always be the minimum. If the element at the ith index is the smallest, then we can safely say, that element at the ith index will be the minimum in the (i+1)*(N-i) subarray. So, its total contribution will be arr[i]*(i+1)*(N-i). Now, we will divide the array into two parts (0,i-1) and (i+1,N-1) and apply the same algorithm on both separately. So our general recurrence relation will be

minSumSubarray(arr, l, r) = arr[i]*(r-i+1)*(i-l+1) 
                            + minSumSubarray(arr, l, i-1)
                            + minSumSubarray(arr, i+1, r)
where i is index of minimum element in range [l,r].

Now, we need a way to answer rangemin() questions efficiently. Segmented trees would be an effective way to answer this question. We have to answer this question maximum N times. Thus, the time complexity of our divide and conquer algorithm will be O(Nlog(N)).

Let’s understand more using the code.

#include <bits/stdc++.h>
#define MAX_SEG_TREE_SIZE 51
using namespace std;

// Array to store the segment tree.
// In the first pair, we will store the minimum of a range.
// In the second pair, we will store the index of that range.
pair<int, int> seg_tree[MAX_SEG_TREE_SIZE];

// Size of the array declared globally to maintain simplicity in code
int n;

// Function to build the segment tree
pair<int, int> buildMinTree(int left, int right, int node, int arr[])
{
    // Base case
    if (left == right)
    {
        seg_tree[node] = {arr[left], left};
        return seg_tree[node];
    }

    // Finding the minimum among the left and right child
    seg_tree[node] = min(buildMinTree(left, (left + right) / 2, 2 * node + 1, arr),
                         buildMinTree((left + right) / 2 + 1, right, 2 * node + 2, arr));

    // Returning the minimum to the parent
    return seg_tree[node];
}

// Function to perform a range-min query in the segment tree
pair<int, int> rangeMin(int query_left, int query_right, int arr[],
                         int node = 0, int segment_left = 0, int segment_right = n - 1)
{
    // Base cases
    if (segment_right < query_left || segment_left > query_right)
        return {INT_MAX, -1};
    if (segment_left >= query_left && segment_right <= query_right)
        return seg_tree[node];

    // Finding the minimum among the left and right child
    return min(rangeMin(query_left, query_right, arr, 2 * node + 1, segment_left, (segment_left + segment_right) / 2),
               rangeMin(query_left, query_right, arr, 2 * node + 2, (segment_left + segment_right) / 2 + 1, segment_right));
}

// Function to find the minimum sum subarray
int minSumSubarray(int arr[], int left = 0, int right = n - 1)
{
    // Base case
    if (left > right)
        return 0;

    // Range-min query to determine the smallest element in the range.
    pair<int, int> min_range = rangeMin(left, right, arr);

    // Dividing the array into two parts
    return min_range.first * (right - min_range.second + 1) * (min_range.second - left + 1) +
           minSumSubarray(arr, left, min_range.second - 1) +
           minSumSubarray(arr, min_range.second + 1, right);
}

// Driver function
int main()
{
    // Input array
    int arr[] = {2, 4, 6, 8, 10};

    // Size of the array
    n = sizeof(arr) / sizeof(int);

    // Building the segment tree
    buildMinTree(0, n - 1, 0, arr);

    // Required answer
    cout << minSumSubarray(arr);

    return 0;
}

Output :

75

Time complexity : O(Nlog(N))