maximum-sum-with-at-most-k-elements

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Sort each row in descending order and extract the top <code>limits[i]</code> elements.

Use a max-heap to efficiently pick the largest <code>k</code> elements across all rows.

Algorithms

You are given a 2D integer matrix <code>grid</code> of size <code>n x m</code>, an integer array <code>limits</code> of length <code>n</code>, and an integer <code>k</code>. The task is to find the maximum sum of at most <code>k</code> elements from the matrix <code>grid</code> such that:

<ul data-spread="false">
	<li>
	The number of elements taken from the <code>ith</code> row of <code>grid</code> does not exceed <code>limits[i]</code>.
	</li>
</ul>

Return the maximum sum.

&nbsp;
Example 1:

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

Output: 7

Explanation:

<ul>
	<li>From the second row, we can take at most 2 elements. The elements taken are 4 and 3.</li>
	<li>The maximum possible sum of at most 2 selected elements is <code>4 + 3 = 7</code>.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3

Output: 21

Explanation:

<ul>
	<li>From the first row, we can take at most 2 elements. The element taken is 7.</li>
	<li>From the second row, we can take at most 2 elements. The elements taken are 8 and 6.</li>
	<li>The maximum possible sum of at most 3 selected elements is <code>7 + 8 + 6 = 21</code>.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>n == grid.length == limits.length</code></li>
	<li><code>m == grid[i].length</code></li>
	<li><code>1 &lt;= n, m &lt;= 500</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 105</code></li>
	<li><code>0 &lt;= limits[i] &lt;= m</code></li>
	<li><code>0 &lt;= k &lt;= min(n * m, sum(limits))</code></li>
</ul>

第 438 场周赛

weekly-contest-438

maxSum

高级工程师

Maximum Sum With at Most K Elements

Greedy

Array

Matrix

Sorting

Heap (Priority Queue)

给你一个大小为 <code>n x m</code>&nbsp;的二维矩阵&nbsp;<code>grid</code>&nbsp;，以及一个长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>limits</code>&nbsp;，和一个整数&nbsp;<code>k</code>&nbsp;。你的目标是从矩阵 <code>grid</code> 中提取出&nbsp;至多 <code>k</code>&nbsp;个元素，并计算这些元素的最大总和，提取时需满足以下限制：

<ul data-spread="false">
	<li>
	从 <code>grid</code>&nbsp;的第 <code>i</code> 行提取的元素数量不超过 <code>limits[i]</code> 。
	</li>
</ul>

返回最大总和。

&nbsp;

示例 1：

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

输出：7

解释：

<ul>
	<li>从第 2 行提取至多 2 个元素，取出 4 和 3 。</li>
	<li>至多提取 2 个元素时的最大总和&nbsp;<code>4 + 3 = 7</code>&nbsp;。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入：grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3

输出：21

解释：

<ul>
	<li>从第 1&nbsp;行提取至多 2 个元素，取出 7 。</li>
	<li>从第 2 行提取至多 2 个元素，取出&nbsp;8 和 6 。</li>
	<li>至多提取 3&nbsp;个元素时的最大总和 <code>7 + 8 + 6 = 21</code>&nbsp;。</li>
</ul>
</div>

&nbsp;

提示：

<ul>
	<li><code>n == grid.length == limits.length</code></li>
	<li><code>m == grid[i].length</code></li>
	<li><code>1 &lt;= n, m &lt;= 500</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 105</code></li>
	<li><code>0 &lt;= limits[i] &lt;= m</code></li>
	<li><code>0 &lt;= k &lt;= min(n * m, sum(limits))</code></li>
</ul>

提取至多 K 个元素的最大总和

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给你一个大小为 n x m 的二维矩阵 grid ，以及一个长度为 n 的整数数组 limits ，和一个整数 k 。你的目标是从矩阵 grid 中提取出 至多 k 个元素，并计算这些元素的最大总和，提取时需满足以下限制：

 * 从 grid 的第 i 行提取的元素数量不超过 limits[i] 。

返回最大总和。

 

示例 1：

输入：grid = [[1,2],[3,4]], limits = [1,2], k = 2

输出：7

解释：

 * 从第 2 行提取至多 2 个元素，取出 4 和 3 。
 * 至多提取 2 个元素时的最大总和 4 + 3 = 7 。

示例 2：

输入：grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3

输出：21

解释：

 * 从第 1 行提取至多 2 个元素，取出 7 。
 * 从第 2 行提取至多 2 个元素，取出 8 和 6 。
 * 至多提取 3 个元素时的最大总和 7 + 8 + 6 = 21 。

 

提示：

 * n == grid.length == limits.length
 * m == grid[i].length
 * 1 <= n, m <= 500
 * 0 <= grid[i][j] <= 105
 * 0 <= limits[i] <= m
 * 0 <= k <= min(n * m, sum(limits))