题目描述
给定一个整数数组 A ,考虑 A 的所有非空子序列。
对于任意序列 S ,设 S 的宽度是 S 的最大元素和最小元素的差。
返回 A 的所有子序列的宽度之和。
由于答案可能非常大,请返回答案模 10^9+7。
样例
输入:[2,1,3]
输出:6
解释:
子序列为 [1],[2],[3],[2,1],[2,3],[1,3],[2,1,3]。
相应的宽度是 0,0,0,1,1,2,2。
这些宽度之和是 6。
数学 $O(nlogn)$
题目要求的是所有子序列的宽度,即
结果 = 子序列 0 的宽度 + 子序列 1 的宽度 + 子序列 2 的宽度 + … + 子序列 n 的宽度
把上面这个式子的宽度用公式展开
结果 = 子序列 0 的最大值 - 子序列 0 的最小值 + 子序列 1 的最大值 - 子序列 1 的最小值 + … + 子序列 n 的最大值 - 子序列 n 的最小值
= 子序列 0 的最大值 + 子序列 1 的最大值 + … + 子序列 n 的最大值 + 子序列 0 的最小值 + 子序列 1 的最小值 + … + 子序列 n 的最小值
= 所有子序列的最大值之和 - 所有子序列的最小值之和
经过上述转换,问题变成了:
(1)如何求所有子序列的最大值之和?
(2)如何求所有子序列的最小值之和?
上述 2 个问题具有对称性,只分析第一个问题即可。
从左到右依次遍历数组中每一个元素,对于某个元素 nums[i],假设在 [0, i - 1] 范围内有 a 个元素小于等于 nums[i],在 [i + 1, n - 1] 范围内有 b 个元素小于 nums[i],那么以 nums[i] 为最大值的子序列的个数有 2^(a + b)。
我们将数组排序,
nums[i]左侧有i个元素,均小于nums[i] 故以nums[i]为最大值
nums[i]左侧有n-1-i个元素,均大于nums[i] 故以nums[i]为最小值
递推公式呼之欲出:
记得最后要取余!!!
时间复杂度
参考文献
Python 代码
class Solution:
def sumSubseqWidths(self, nums: List[int]) -> int:
n = len(nums)
MOD = 10**9 + 7
nums = sorted(nums)
res = 0
t = [1]
for i in range(n):
t.append((t[-1]*2)%MOD)
for i in range(n):
res += ((t[i]-t[n-i-1])*nums[i])
res %= MOD
return res