求所有可能子数组的最大差值之和

Question

求给定数组的连续子集的最大可能差之和。

我们得到一个由n个非负整数（允许重复元素）组成的数组arr[]，求出给定数组中相邻子集的最大差之和。

假设max（s）表示任何子集's'中的最大值，而min（s）表示集合's'中的最小值。我们需要为所有可能的子集找到max（s）-min（s）的总和。

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

解释：

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.

约束条件：

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

这是从此处获取的代码，但此代码检查所有可能的子集，而不是连续的子集：

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;
    }

那么如何只得到连续的子集并以更低的时间复杂度解决这个问题。

Answer 1

您可以使用流来实现这一点：

public static int difference(int[] arr) {
    int size = arr.length;
    
    return IntStream.range(0, size)
            .flatMap(i -> IntStream.range(i + 1, size)
                    .mapToObj(j -> Arrays.stream(arr, i, j + 1).summaryStatistics())
                    .mapToInt(stat -> stat.getMax() - stat.getMin()))
            .sum();
}

或者，正如@kcsquare所注意到的，您可以使用2个stream，一个用于最大和，另一个用于最小和，并减去它们。这种方法还避免了不必要的装箱和解箱。

public static int difference2(int[] arr) {
    int size = arr.length;
            
    int max = IntStream.range(0, size)
            .flatMap(i -> IntStream.range(i + 1, size)
                    .map(j -> Arrays.stream(arr, i, j + 1).max().getAsInt()))
            .sum();
    
    int min = IntStream.range(0, size)
            .flatMap(i -> IntStream.range(i + 1, size)
                    .map(j -> Arrays.stream(arr, i, j + 1).min().getAsInt()))
            .sum();
    return max - min;
}

Answer 2

让我们使用归纳法。

• 假设我们以某种方式解决了大小为N的数组的问题，并且知道所需的和
• 如果元素A[n 1]被添加，那么我们来寻找解决方案
• 我们只需要计算包含[n 1]的所有序列的和。
  • A[0]，A[1]，A[2]。。。，A【n 1】
  • A[1]，A[2]。。。，A【n 1】
  • A【n】、A【n 1】
  • A【n 1】，A【n】

  int a[] = {1, 2, 3};
  
  long sum = 0;
  for (int i = 1; i < a.length; i++) {
      int min = a[i];
      int max = a[i];
  
      for (int j = i - 1; j >= 0; j--) {
          int current = a[j];
          if (current < min) min = current;
          if (current > max) max = current;
          sum += max - min;
      }
   }
   
   System.out.println("Sum = " + sum);
  

Answer 3

您可以在时间和空间中执行此操作。

该技术是对所有最近的较小值使用该算法。首先，将问题分为两部分：

1. 求所有子数组最大值的和
2. 找到所有子数组最小值的总和，并将其从第一个总和中减去。

这两个问题的解决方案是相同的，除了用“大于”交换所有出现的“小于”，所以我只描述最小值的情况。

对于数组中的每个元素，您可以问：“有多少子数组的最小元素是？”为了处理重复项，假设我们总是将子数组中最小元素最右边的匹配项作为“代表”元素。

这个问题转化为：在看到一个严格小于A[i]的元素之前，我们可以走到A[i]的左边多远，在看到一个小到A[i]的元素之前，我们可以走到A[i]的右边多远。将这两个距离相乘，以获得子阵列中所有可能的左endpoint和右endpoint选择，这些子阵列的最小元素为A[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]))

例如，在这个问题的答案中有几个最接近的较小值的实现，在维基百科的文章中有伪代码。要查找“下一个较小的值”而不是“前一个较小的值”，只需在一个反向数组上运行该算法（或者只需按反向顺序遍历a，从a[n-1]向下遍历到a[0]）。

整个算法的示例实现（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