Find the sum of maximum difference of all possible subarrays

Question

Find the sum of maximum difference possible from contiguous subset of a given array.

We are given an array arr[] of n non-negative integers (repeated elements allowed), find out the sum of maximum difference possible from contiguous subsets of the given array.

Suppose max(s) represents the maximum value in any subset ‘s’ whereas min(s) represents the minimum value in the set ‘s’. We need to find the sum of max(s)-min(s) for all possible subsets.

Input : arr[] = {1, 2, 3}
Output : result = 4

Explanation :

All possible subset and for each subset s,
max(s)-min(s) are as :
SUBSET    |  max(s) | min(s) | max(s)-min(s)
{1, 2}    |  2      |  1     |   1
{2, 3}    |  3      |  2     |   1
{1, 2, 3} |  3      |  1     |   2
Total Difference sum = 4
Note : max(s) - min(s) for all subset with 
single element must be zero.

Constraints:

Array size can be from 1 to 10 power 5, also each element in array can be from 1 to 10 power 5.

This is the code taken from here, but this code checks all possible subsets instead of contiguous subsets:

public static int MOD = 1000000007;
      
    // function for sum of max min difference 
    public static long maxMin (int arr[], int n) 
    {
        // sort all numbers
        Arrays.sort(arr);
          
        // iterate over array and with help of 
        // horner's rule calc max_sum and min_sum
        long min_sum = 0, max_sum = 0;
        for (int i = 0; i < n; i++)
        {
            max_sum = 2 * max_sum + arr[n - 1 - i];
            max_sum %= MOD;
            min_sum = 2 * min_sum + arr[i];
            min_sum %= MOD;
        }
      
        return (max_sum - min_sum + MOD)%MOD;
    }

So how to get only contiguous subsets and solve this with less time complexity.

Answer 1

You can do this in O(n) time and space.

The technique is to use the algorithm for all nearest smaller values. First, break the problem into two parts:

1. Find the sum of all subarray maximums
2. Find the sum of all subarray minimums, and subtract this from the first sum.

The solution for both problems is identical apart from exchanging all occurrences of 'less than' with 'greater than', so I'll describe the minimums case only.

For each element A[i] of the array, you can ask: 'How many subarrays have A[i] as their minimum element?' To deal with duplicates, assume we always take the rightmost occurrence of a minimum element within a subarray as the 'representative' element.

The question transforms to finding how far to the left of A[i] we can go before seeing an element strictly smaller than A[i], and how far to the right of A[i] we can go before seeing an element as small as A[i]. Multiply these two distances to get all possible choices of left and right endpoints among subarrays that have A[i] as their minimum element. We can find both of these directly with the 'all nearest smaller values' algorithm, and solve the rest of the problem like so (pseudocode):

 1. For each position i in the array A, let previous_smaller[i]
    be the largest index j such that A[j] < A[i] and 0 <= j < i,
    or -1 if there is no such index.

 2. For each position i in the array A, let next_smaller_or_equal[i]
    be the smallest index j such that A[j] <= A[i] and i < j < n,
    or n if there is no such index.

 3. Return the sum over all i, 0 <= i < n, of 
    (A[i] * 
    (next_smaller_or_equal[i] - i) * 
    (i - previous_smaller[i]))

There are several implementations of all nearest smaller values in the answers to this question, for example, and pseudocode in the Wikipedia article. To find 'next smaller values' instead of 'previous smaller values', simply run the algorithm on a reversed array A (or just traverse A in reverse order, from A[n-1] down to A[0]).

Sample implementation of the whole algorithm (in Python):

def max_difference_sum(A: List[int]) -> int:
    """Given an array of integers A, compute the 
    sum over all subarrays B of max(B) - min(B)
    by using nearest smaller values"""
    
    n = len(A)

    # Convention to take the rightmost min or max in each subarray.
    previous_smaller = list(range(n))
    next_smaller_or_equal = list(range(n))

    previous_larger = list(range(n))
    next_larger_or_equal = list(range(n))

    # Compute the previous larger and smaller in a single loop.
    for i in range(n):
        j = i - 1
        while j >= 0 and A[j] >= A[i]:
            j = previous_smaller[j]
        previous_smaller[i] = j

        j = i - 1
        while j >= 0 and A[j] <= A[i]:
            j = previous_larger[j]
        previous_larger[i] = j

    for i in reversed(range(n)):
        j = i + 1
        while j < n and A[j] > A[i]:
            j = next_smaller_or_equal[j]
        next_smaller_or_equal[i] = j

        j = i + 1
        while j < n and A[j] < A[i]:
            j = next_larger_or_equal[j]
        next_larger_or_equal[i] = j

    max_sums = sum(A[i]
                   * (next_larger_or_equal[i] - i)
                   * (i - previous_larger[i])
                   for i in range(n))

    min_sums = sum(A[i]
                   * (next_smaller_or_equal[i] - i)
                   * (i - previous_smaller[i])
                   for i in range(n))
    
    return max_sums - min_sums