maximum-and-minimum-sums-of-at-most-size-k-subsequences

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>nums</code> and a positive integer <code>k</code>. Return the sum of the maximum and minimum elements of all subsequences of <code>nums</code> with at most <code>k</code> elements.

Since the answer may be very large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,2,3], k = 2

Output: 24

Explanation:

The subsequences of <code>nums</code> with at most 2 elements are:

<table style="border: 1px solid black;">
	<tbody>
		<tr>
			<th style="border: 1px solid black;">Subsequence </th>
			<th style="border: 1px solid black;">Minimum</th>
			<th style="border: 1px solid black;">Maximum</th>
			<th style="border: 1px solid black;">Sum</th>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[1]</code></td>
			<td style="border: 1px solid black;">1</td>
			<td style="border: 1px solid black;">1</td>
			<td style="border: 1px solid black;">2</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[2]</code></td>
			<td style="border: 1px solid black;">2</td>
			<td style="border: 1px solid black;">2</td>
			<td style="border: 1px solid black;">4</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[3]</code></td>
			<td style="border: 1px solid black;">3</td>
			<td style="border: 1px solid black;">3</td>
			<td style="border: 1px solid black;">6</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[1, 2]</code></td>
			<td style="border: 1px solid black;">1</td>
			<td style="border: 1px solid black;">2</td>
			<td style="border: 1px solid black;">3</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[1, 3]</code></td>
			<td style="border: 1px solid black;">1</td>
			<td style="border: 1px solid black;">3</td>
			<td style="border: 1px solid black;">4</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[2, 3]</code></td>
			<td style="border: 1px solid black;">2</td>
			<td style="border: 1px solid black;">3</td>
			<td style="border: 1px solid black;">5</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;">Final Total</td>
			<td style="border: 1px solid black;">&nbsp;</td>
			<td style="border: 1px solid black;">&nbsp;</td>
			<td style="border: 1px solid black;">24</td>
		</tr>
	</tbody>
</table>

The output would be 24.
</div>

Example 2:

<div class="example-block">
Input: nums = [5,0,6], k = 1

Output: 22

Explanation: 

For subsequences with exactly 1 element, the minimum and maximum values are the element itself. Therefore, the total is <code>5 + 5 + 0 + 0 + 6 + 6 = 22</code>.
</div>

Example 3:

<div class="example-block">
Input: nums = [1,1,1], k = 2

Output: 12

Explanation:

The subsequences <code>[1, 1]</code> and <code>[1]</code> each appear 3 times. For all of them, the minimum and maximum are both 1. Thus, the total is 12.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= min(70, nums.length)</code></li>
</ul>

minMaxSums

Maximum and Minimum Sums of at Most Size K Subsequences

Array

Math

Dynamic Programming

Combinatorics

Sorting

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

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

由于答案可能非常大，请返回对 <code>109 + 7</code> 取余数的结果。

&nbsp;

示例 1：

<div class="example-block">
输入： nums = [1,2,3], k = 2

输出： 24

解释：

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

<table style="border: 1px solid black; border-collapse: collapse;">
	<thead>
		<tr>
			<th style="border: 1px solid black;">子序列</th>
			<th style="border: 1px solid black;">最小值</th>
			<th style="border: 1px solid black;">最大值</th>
			<th style="border: 1px solid black;">和</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td style="border: 1px solid black;"><code>[1]</code></td>
			<td style="border: 1px solid black;">1</td>
			<td style="border: 1px solid black;">1</td>
			<td style="border: 1px solid black;">2</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[2]</code></td>
			<td style="border: 1px solid black;">2</td>
			<td style="border: 1px solid black;">2</td>
			<td style="border: 1px solid black;">4</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[3]</code></td>
			<td style="border: 1px solid black;">3</td>
			<td style="border: 1px solid black;">3</td>
			<td style="border: 1px solid black;">6</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[1, 2]</code></td>
			<td style="border: 1px solid black;">1</td>
			<td style="border: 1px solid black;">2</td>
			<td style="border: 1px solid black;">3</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[1, 3]</code></td>
			<td style="border: 1px solid black;">1</td>
			<td style="border: 1px solid black;">3</td>
			<td style="border: 1px solid black;">4</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;"><code>[2, 3]</code></td>
			<td style="border: 1px solid black;">2</td>
			<td style="border: 1px solid black;">3</td>
			<td style="border: 1px solid black;">5</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;">总和</td>
			<td style="border: 1px solid black;">&nbsp;</td>
			<td style="border: 1px solid black;">&nbsp;</td>
			<td style="border: 1px solid black;">24</td>
		</tr>
	</tbody>
</table>

因此，输出为 24。
</div>

示例 2：

<div class="example-block">
输入： nums = [5,0,6], k = 1

输出： 22

解释：

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

示例 3：

<div class="example-block">
输入： nums = [1,1,1], k = 2

输出： 12

解释：

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

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= min(100, nums.length)</code></li>
</ul>

子序列	最小值	最大值	和
`[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