Maximum and Minimum Sums of at Most Size K Subsequences - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3428. Maximum and Minimum Sums of at Most Size K Subsequences
Medium
30 Points
Array
Math
Dynamic Programming
Sorting
Combinatorics
You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all subsequences of nums with at most k elements.
Since the answer may be very large, return it modulo 109 + 7.
Examples
Example 1
Input: nums = [1,2,3], k = 2
Output: 24
Explanation:
The subsequences of nums with at most 2 elements are:
The output would be 24.
Example 2
Input: nums = [5,0,6], k = 1
Output: 2 2
Explanation:
For subsequences with exactly 1 element, the minimum and maximum values are the element itself. Therefore, the total is 5 + 5 + 0 + 0 + 6 + 6 = 22 .
Example 3
Input: nums = [1,1,1], k = 2
Output: 12
Explanation:
The subsequences [1, 1] and [1] each appear 3 times. For all of them, the minimum and maximum are both 1. Thus, the total is 12.
Constraints
1 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= min(70, nums.length)
3428. Maximum and Minimum Sums of at Most Size K Subsequences
Medium
30 Points
Array
Math
Dynamic Programming
Sorting
Combinatorics
You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all subsequences of nums with at most k elements.
Since the answer may be very large, return it modulo 109 + 7.
Examples
Example 1
Input: nums = [1,2,3], k = 2
Output: 24
Explanation:
The subsequences of nums with at most 2 elements are:
The output would be 24.
Example 2
Input: nums = [5,0,6], k = 1
Output: 2 2
Explanation:
For subsequences with exactly 1 element, the minimum and maximum values are the element itself. Therefore, the total is 5 + 5 + 0 + 0 + 6 + 6 = 22 .
Example 3
Input: nums = [1,1,1], k = 2
Output: 12
Explanation:
The subsequences [1, 1] and [1] each appear 3 times. For all of them, the minimum and maximum are both 1. Thus, the total is 12.