3428. 最多 K 个元素的子序列的最值之和

题目描述

给你一个整数数组 nums 和一个正整数 k，返回所有长度最多为 k 的 子序列 中 最大值 与 最小值 之和的总和。

非空子序列 是指从另一个数组中删除一些或不删除任何元素（且不改变剩余元素的顺序）得到的数组。

由于答案可能非常大，请返回对 10⁹ + 7 取余数的结果。

示例 1：

输入： nums = [1,2,3], k = 2

输出： 24

解释：

数组 nums 中所有长度最多为 2 的子序列如下：

因此，输出为 24。

示例 2：

输入： nums = [5,0,6], k = 1

输出： 22

解释：

对于长度恰好为 1 的子序列，最小值和最大值均为元素本身。因此，总和为 5 + 5 + 0 + 0 + 6 + 6 = 22。

示例 3：

输入： nums = [1,1,1], k = 2

输出： 12

解释：

子序列 [1, 1] 和 [1] 各出现 3 次。对于所有这些子序列，最小值和最大值均为 1。因此，总和为 12。

提示：

思考

统计所有长度不超过 \(k\) 的子序列中最大值之和与最小值之和。\(n\le 10^5\)，\(k\le 100\)，不能枚举子序列。

把数组排序后，每个元素作为最大值（最小值）的次数，等于在它左侧（右侧）再选至多 \(k-1\) 个元素的组合数。

因此排序后枚举 \(a_i\)，累加 \(a_i\cdot\sum_{j=0}^{\min(i,k-1)}C(i,j)\) 作为最大贡献，最小贡献对称。组合数按行递推即可，因为 \(k\) 只有 \(100\)。

Python3JavaC++Go