找到给定数组的连续子集中可能的最大差值之和。
我们有一个由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;
}
如何获取仅连续子集并在较短时间内解决此问题。