LeetCode 题解工作台
最多 K 个元素的子序列的最值之和
给你一个整数数组 nums 和一个正整数 k ，返回所有长度最多为 k 的 子序列 中 最大值 与 最小值 之和的总和。 非空子序列 是指从另一个数组中删除一些或不删除任何元素（且不改变剩余元素的顺序）得到的数组。 由于答案可能非常大，请返回对 10 9 + 7 取余数的结果。 示例 1： 输入： …
5
题型
0
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 nums 和一个正整数 k，返回所有长度最多为 k 的 子序列 中 最大值 与 最小值 之和的总和。
非空子序列 是指从另一个数组中删除一些或不删除任何元素（且不改变剩余元素的顺序）得到的数组。
由于答案可能非常大，请返回对 109 + 7 取余数的结果。
示例 1：
输入： nums = [1,2,3], k = 2
输出： 24
解释：
数组 nums 中所有长度最多为 2 的子序列如下：
| 子序列 | 最小值 | 最大值 | 和 |
|---|---|---|---|
[1] |
1 | 1 | 2 |
[2] |
2 | 2 | 4 |
[3] |
3 | 3 | 6 |
[1, 2] |
1 | 2 | 3 |
[1, 3] |
1 | 3 | 4 |
[2, 3] |
2 | 3 | 5 |
| 总和 | 24 |
因此，输出为 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。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 1091 <= k <= min(100, nums.length)
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates understanding of dynamic programming and state transitions.
- question_mark
The candidate suggests sorting the array as a means to simplify subsequence generation.
- question_mark
The candidate efficiently handles the modulo operation to ensure correct results for large sums.
常见陷阱
外企场景- error
Forgetting to apply the modulo operation may lead to incorrect results.
- error
Not sorting the array, which leads to inefficient subsequence calculations.
- error
Overlooking edge cases, such as when k equals 1 or when nums contains duplicate values.
进阶变体
外企场景- arrow_right_alt
Adjusting the value of k to examine subsequences of varying sizes.
- arrow_right_alt
Changing the problem to find only the maximum or minimum sums.
- arrow_right_alt
Modifying the problem to return only the sum for a specific subsequence size.