# 3428. 至多 K 个子序列的最大和最小和

### 题目地址(3428. 至多 K 个子序列的最大和最小和 - 力扣（LeetCode）)

### 题目描述

给你一个整数数组 `nums` 和一个整数 `k`，请你返回一个整数，表示从数组中选取 **至多 k 个子序列**，所有可能方案中，子序列的 **最大值之和** 加上 **最小值之和** 的结果。由于结果可能很大，请返回对 (10^9 + 7) 取模后的值。

一个数组的 **子序列** 是指通过删除一些（可以是 0 个）元素后剩下的序列，且不改变其余元素的相对顺序。例如，`[1, 3]` 是 `[1, 2, 3]` 的子序列，而 `[2, 1]` 不是。

**示例 1：**

```
输入：nums = [1,2,3], k = 2
输出：12
解释：
所有可能的至多 k=2 个子序列方案：
- 空子序列 []：最大值和最小值都记为 0
- [1]：最大值 1，最小值 1
- [2]：最大值 2，最小值 2
- [3]：最大值 3，最小值 3
- [1,2]：最大值 2，最小值 1
- [1,3]：最大值 3，最小值 1
- [2,3]：最大值 3，最小值 2
- [1,2,3]：最大值 3，最小值 1
最大值之和 = 0 + 1 + 2 + 3 + 2 + 3 + 3 + 3 = 17
最小值之和 = 0 + 1 + 2 + 3 + 1 + 1 + 2 + 1 = 11
总和 = 17 + 11 = 28 % (10^9 + 7) = 28
由于 k=2，实际方案数不会超过 k，但这里考虑了所有子序列，结果仍正确。
```

**示例 2：**

```
输入：nums = [2,2], k = 3
输出：12
解释：
所有可能的至多 k=3 个子序列方案：
- []：最大值 0，最小值 0
- [2]（第一个）：最大值 2，最小值 2
- [2]（第二个）：最大值 2，最小值 2
- [2,2]：最大值 2，最小值 2
最大值之和 = 0 + 2 + 2 + 2 = 6
最小值之和 = 0 + 2 + 2 + 2 = 6
总和 = 6 + 6 = 12 % (10^9 + 7) = 12
```

**提示：**

* (1 \leq nums.length \leq 10^5)
* (1 \leq nums\[i] \leq 10^9)
* (1 \leq k \leq 10^5)

***

### 前置知识

* 组合数学：组合数 (C(n, m)) 表示从 (n) 个元素中选 (m) 个的方案数。
* 贡献法

### 思路

这道题要求计算所有至多 (k) 个子序列的最大值之和与最小值之和。数组的顺序对每个元素的贡献没有任何影响，因此我们可以先对数组进行排序，然后计算每个元素作为最大值或最小值的贡献。

我们可以从贡献的角度来思考：对于数组中的每个元素，它在所有可能的子序列中作为最大值或最小值的次数是多少？然后将这些次数乘以元素值，累加起来即可。

#### 分析

1. **子序列的性质**：
   * 一个子序列的最大值是其中最大的元素，最小值是最小的元素。
   * 对于一个有序数组 (nums)，若元素 (nums\[i]) 是子序列的最大值，则子序列只能从 (nums\[0]) 到 (nums\[i]) 中选取，且必须包含 (nums\[i])。
   * 若 (nums\[i]) 是子序列的最小值，则子序列只能从 (nums\[i]) 到 (nums\[n-1]) 中选取，且必须包含 (nums\[i])。
2. **组合计数**：
   * 假设数组已排序（从小到大），对于 (nums\[i])：
     * 作为最大值的子序列：从前 (i) 个元素中选 (j) 个（(0 \leq j < \min(k, i+1))），再加上 (nums\[i])，总方案数为 (\sum\_{j=0}^{\min(k, i)} C(i, j))。
     * 作为最小值的子序列：从后 (n-i-1) 个元素中选 (j) 个（(0 \leq j < \min(k, n-i))），再加上 (nums\[i])，总方案数为 (\sum\_{j=0}^{\min(k, n-i-1)} C(n-i-1, j))。
   * 这里 (C(n, m)) 表示组合数，即从 (n) 个元素中选 (m) 个的方案数。
3. **优化组合计算**：
   * 由于 (n) 和 (k) 可达 (10^5)，直接用 (math.comb) 会超时，且需要取模。
   * 使用预计算阶乘和逆元的方法，快速计算 (C(n, m) = n! / (m! \cdot (n-m)!) \mod (10^9 + 7))。
4. **最终公式**：
   * 对每个 (nums\[i])，计算其作为最大值的贡献和最小值的贡献，累加后取模。

#### 步骤

1. 对数组 (nums) 排序。
2. 预计算阶乘 (fac\[i]) 和逆元 (inv\_f\[i])。
3. 遍历 (nums)：
   * 计算 (nums\[i]) 作为最大值的次数，乘以 (nums\[i])，加到答案中。
   * 计算 (nums\[i]) 作为最小值的次数，乘以 (nums\[i])，加到答案中。
4. 返回结果对 (10^9 + 7) 取模。

***

### 代码

代码支持 Python3：

Python3 Code:

```python
MOD = int(1e9) + 7

# 预计算阶乘和逆元
MX = 100000
fac = [0] * MX  # fac[i] = i!
fac[0] = 1
for i in range(1, MX):
    fac[i] = fac[i - 1] * i % MOD

inv_f = [0] * MX  # inv_f[i] = i!^-1
inv_f[-1] = pow(fac[-1], -1, MOD)
for i in range(MX - 1, 0, -1):
    inv_f[i - 1] = inv_f[i] * i % MOD

# 计算组合数 C(n, m)
def comb(n: int, m: int) -> int:
    if m < 0 or m > n:
        return 0
    return fac[n] * inv_f[m] * inv_f[n - m] % MOD

class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        nums.sort()  # 排序，便于计算最大值和最小值贡献
        ans = 0
        n = len(nums)
        
        # 计算每个元素作为最大值的贡献
        for i, x in enumerate(nums):
            s = sum(comb(i, j) for j in range(min(k, i + 1))) % MOD
            ans += x * s
            
        # 计算每个元素作为最小值的贡献
        for i, x in enumerate(nums):
            s = sum(comb(n - i - 1, j) for j in range(min(k, n - i))) % MOD
            ans += x * s
            
        return ans % MOD
```

***

**复杂度分析**

* **时间复杂度**：(O(n \log n + n \cdot k))
  * 排序：(O(n \log n))。
  * 预计算阶乘和逆元：(O(MX))，(MX = 10^5) 是常数。
  * 遍历 (nums) 并计算组合和：(O(n \cdot k))，因为对于每个 (i)，需要计算最多 (k) 个组合数。
* **空间复杂度**：(O(MX))，用于存储阶乘和逆元数组。

***

### 总结

这道题的关键在于理解子序列的最大值和最小值的贡献，并利用组合数学计算每个元素出现的次数。预计算阶乘和逆元避免了重复计算组合数的开销，使得代码能在时间限制内运行。排序后分别处理最大值和最小值贡献，是一个清晰且高效的思路。

如果你有其他解法或疑问，欢迎讨论！