0891. Sum of Subsequence Widths

题目信息

题号:

0891

难度:

Hard

主题:

数组、非空子序列、极值差

原题:

LeetCode 0891

重点:

每个非空下标子集形成一个子序列,宽度为最大值减最小值;相同数值位于不同下标时仍产生不同子序列实例

题目重述

给定整数数组 nums。从中选择任意非空下标集合,并按原下标顺序保留对应元素,可以得到一个非空子序列。该子序列的宽度定义为其中最大元素与最小元素之差。

请把所有非空子序列的宽度相加,并返回总和对 10^9 + 7 取模后的结果。选择的下标集合不同就属于不同子序列,即使它们产生了相同的数值序列或相同宽度,也要分别计数。

1 <= nums.length <= 10^5,1 <= nums[i] <= 10^5。

自建示例

列出全部多元素子序列:

输入:nums = [1,2,4]
输出:9
解释:三个单元素子序列宽度均为 0;三个二元素子序列宽度分别为 1、3、2,三元素子序列宽度为 3,总和为 0 + 1 + 3 + 2 + 3 = 9。

所有数值都相等:

输入:nums = [5,5]
输出:0
解释:两个单元素子序列和由两个位置组成的子序列中,最大值与最小值都相等,所有宽度均为 0;不同下标子序列仍分别存在,但总和不变。