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

Question

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

\n

给定一个由 n 个非负整数组成的数组 arr[]（允许重复元素），找出给定数组的连续子集可能的最大差值之和。

\n

假设 max(s) 表示任何子集 \xe2\x80\x98s\xe2\x80\x99 中的最大值，而 min(s) 表示集合 \xe2\x80\x98s\xe2\x80\x99 中的最小值。我们需要找到所有可能子集的 max(s)-min(s) 之和。

\n

Input : arr[] = {1, 2, 3}\nOutput : result = 4\n

\n

解释 ：

\n

All possible subset and for each subset s,\nmax(s)-min(s) are as :\nSUBSET    |  max(s) | min(s) | max(s)-min(s)\n{1, 2}    |  2      |  1     |   1\n{2, 3}    |  3      |  2     |   1\n{1, 2, 3} |  3      |  1     |   2\nTotal Difference sum = 4\nNote : max(s) - min(s) for all subset with \nsingle element must be zero.\n

\n

限制条件：

\n

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

\n

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

\n

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

\n

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

\n

Answer 1

你可以在O(n)时间和空间上做到这一点。

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

1. 求所有子数组最大值的总和
2. 求所有子数组最小值的总和，然后从第一个总和中减去该总和。

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

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

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

整个算法的示例实现（Python）：

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

Answer 2

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