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

Question

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

10

找到给定数组的连续子集中可能的最大差值之和。

我们有一个由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;
    }

如何获取仅连续子集并在较短时间内解决此问题。

- learner

“连续”位实际上是什么意思？如果您只选择数组的“整个数组”作为连续子集，其中包含最小值和最大值，则它们的总和就是答案？ - Andy Turner

@AndyTurner，这里的连续指的是相邻的元素。例如，在数组[1,2,3]中，子集[1,3]在我的情况下无效，因为它们不是相邻的。有效的子集是[1,2]，[2,3]，[1,2,3]。 - learner

因此，整个数组是整个数组的连续（非严格）子集，其最大和最小元素具有最大差异。 - Andy Turner

根据我的帖子，我需要所有最大值和最小值之差的总和。根据您的评论，我了解到对于数组[1,2.3]，最大值为3，最小值为1，因此最大值-最小值= 3-1 = 2。但在我的情况下，应该是4，正如我在帖子中所提到的。 - learner

出于好奇，这个问题有特定的实际应用吗？还是仅仅是学术演习？ - eliangius

你要找的时间复杂度是什么？ - user1984

4个回答

2

让我们使用归纳法。

Assume we solved the problem somehow for the array of size N and know the desired sum.
Let's find the solution if the element A[n+1] is added.
We need to calculate the sums only for all sequences that include A[n+1].
- A[0], A[1], A[2], ..., A[n+1]
- A[1], A[2], ..., A[n+1]
- ...
- A[n], A[n+1]
All other contiguous subsets were calculated at the previous step somehow.
In order to calculate their minimums and maximums let's examine them in the reverse order.
- A[n+1], A[n]
- A[n+1], A[n], A[n-1]
- ...
- A[n+1], A[n], ..., A[0]
This gives us an ability to iterate them and find their extremes in a single loop.

So the code is

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

The solution complexity is O(n^2) as there are two nested loops.

- Andriy Slobodyanyk

我在从引导方法到最终代码的路径上迷失了方向，大概是在第3步和第5步之间。尽管如此，代码能够运行，所以原因一定是我的能力有限... - tquadrat

1

您可以使用stream实现此操作：

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

另外，正如@kcsquared所指出的那样，您可以使用2个stream，一个用于最大和，另一个用于最小和，并将它们相减。这种方法还避免了不必要的boxing和unboxing。

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

- Oboe

0

由于提出的部分解决方案已经支付了排序成本，因此可以进行初始时间优化，将输入arr预转换为(i，arr [i])列表，然后按arr [i]值进行排序，并在for循环中跳过具有非连续i值的已排序元组数组。

- eliangius

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kcsquared · Accepted Answer

您可以在O(n)时间和空间内完成此操作。

技术是使用all nearest smaller values算法。首先，将问题分为两部分：

找到所有子数组最大值的总和
找到所有子数组最小值的总和，并从第一个总和中减去这个总和。

两个问题的解决方案除了将所有“小于”替换为“大于”外都是相同的，因此我只描述最小值的情况。

对于数组的每个元素A[i]，您可以问：“有多少子数组以A[i]作为它们的最小元素？”为了处理重复项，假设我们始终将子数组中最小元素的最右出现作为“代表性”元素。

问题转化为找到离A[i]左侧最远的严格小于A[i]的元素，以及找到离A[i]右侧最远的与A[i]一样小的元素。将这两个距离相乘即可得到以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）。

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