0891. Sum of Subsequence Widths¶
题目信息¶
- 题号:
0891
- 难度:
Hard
- 主题:
数组、非空子序列、极值差
- 原题:
- 重点:
每个非空下标子集形成一个子序列,宽度为最大值减最小值;相同数值位于不同下标时仍产生不同子序列实例
题目重述¶
给定整数数组 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;不同下标子序列仍分别存在,但总和不变。