Skip to main content
AI Assist is now on Stack Overflow. Start a chat to get instant answers from across the network. Sign up to save and share your chats.

Return to Answer

Bounty Awarded with 25 reputation awarded by CommunityBot
fixed typo in pseudocode
Source Link
kcsquared
kcsquared
  • 5.4k
  • 1
  • 13
  • 36
 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_larger_or_equal[i]next_smaller_or_equal[i] - i) * 
    (i - previous_larger[i]previous_smaller[i]))

 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_larger_or_equal[i] - i) * 
    (i - previous_larger[i]))

 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]))
Added Python code
Source Link
kcsquared
kcsquared
  • 5.4k
  • 1
  • 13
  • 36

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

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
Source Link
kcsquared
kcsquared
  • 5.4k
  • 1
  • 13
  • 36

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_larger_or_equal[i] - i) * 
    (i - previous_larger[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]).