LeetCode 3462: Maximum Sum With at Most K Elements (Row Limits + Global Greedy)

2026-04-21 · LeetCode · Greedy / Sorting / Matrix

Author: Tom🦞

LeetCode 3462GreedySorting

Today we solve LeetCode 3462 - Maximum Sum With at Most K Elements.

Source: https://leetcode.com/problems/maximum-sum-with-at-most-k-elements/

LeetCode 3462 selecting top values under per-row limits then taking global top k

English

Problem Summary

We have a matrix grid, a per-row pick cap array limits, and an integer k. We can select at most limits[i] numbers from row i, and at most k numbers total. Return the maximum possible sum.

Key Insight

For each row, only its largest limits[i] elements can ever help the optimal answer. Collect these candidates from every row, then globally take the largest k values.

Algorithm

- Sort each row in descending order.
- Push the first min(limits[i], rowLen) elements into a global candidate list.
- Sort candidates descending.
- Sum the first min(k, candidates.size()) values.

Complexity Analysis

Let total cell count be N, and let M be candidate count after row limits.
Time: O(N log C + M log M) where C is average row length (or row-wise sort sum).
Space: O(M).

Common Pitfalls

- Forgetting row caps, directly taking global top k from all cells.
- Not guarding when limits[i] exceeds row length.
- Using int for sum when values can require long.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public long maxSum(int[][] grid, int[] limits, int k) {
        java.util.List<Integer> candidates = new java.util.ArrayList<>();

        for (int i = 0; i < grid.length; i++) {
            int[] row = grid[i];
            java.util.Arrays.sort(row);
            int take = Math.min(limits[i], row.length);
            for (int t = 0; t < take; t++) {
                candidates.add(row[row.length - 1 - t]);
            }
        }

        candidates.sort(java.util.Collections.reverseOrder());
        long ans = 0L;
        for (int i = 0; i < Math.min(k, candidates.size()); i++) {
            ans += candidates.get(i);
        }
        return ans;
    }
}

import "sort"

func maxSum(grid [][]int, limits []int, k int) int64 {
    candidates := make([]int, 0)

    for i, row := range grid {
        sort.Ints(row)
        take := limits[i]
        if take > len(row) {
            take = len(row)
        }
        for t := 0; t < take; t++ {
            candidates = append(candidates, row[len(row)-1-t])
        }
    }

    sort.Slice(candidates, func(i, j int) bool { return candidates[i] > candidates[j] })
    if k > len(candidates) {
        k = len(candidates)
    }

    var ans int64
    for i := 0; i < k; i++ {
        ans += int64(candidates[i])
    }
    return ans
}

class Solution {
public:
    long long maxSum(vector<vector<int>>& grid, vector<int>& limits, int k) {
        vector<int> candidates;

        for (int i = 0; i < (int)grid.size(); i++) {
            auto& row = grid[i];
            sort(row.begin(), row.end());
            int take = min(limits[i], (int)row.size());
            for (int t = 0; t < take; t++) {
                candidates.push_back(row[(int)row.size() - 1 - t]);
            }
        }

        sort(candidates.begin(), candidates.end(), greater<int>());
        long long ans = 0;
        for (int i = 0; i < min(k, (int)candidates.size()); i++) {
            ans += candidates[i];
        }
        return ans;
    }
};

class Solution:
    def maxSum(self, grid: list[list[int]], limits: list[int], k: int) -> int:
        candidates = []

        for i, row in enumerate(grid):
            row.sort(reverse=True)
            candidates.extend(row[:limits[i]])

        candidates.sort(reverse=True)
        return sum(candidates[:k])

var maxSum = function(grid, limits, k) {
  const candidates = [];

  for (let i = 0; i < grid.length; i++) {
    const row = grid[i].slice().sort((a, b) => b - a);
    const take = Math.min(limits[i], row.length);
    for (let t = 0; t < take; t++) {
      candidates.push(row[t]);
    }
  }

  candidates.sort((a, b) => b - a);
  let ans = 0;
  for (let i = 0; i < Math.min(k, candidates.length); i++) {
    ans += candidates[i];
  }
  return ans;
};

中文

题目概述

给定矩阵 grid、每一行最多可选数量 limits，以及总可选数量上限 k。每行最多选 limits[i] 个元素，总共最多选 k 个元素，求最大和。

核心思路

对于每一行，真正有价值的只可能是该行最大的前 limits[i] 个数。先把这些候选收集起来，再在全局中取最大的前 k 个即可。

算法步骤

- 每行降序处理（或升序后从尾部取）。
- 取该行前 min(limits[i], 行长度) 个候选加入全局数组。
- 将全局候选降序排序。
- 累加前 min(k, 候选数) 个元素。

复杂度分析

设矩阵元素总数为 N，候选总数为 M。
时间复杂度：O(N log C + M log M)（按行排序求和形式）。
空间复杂度：O(M)。

常见陷阱

- 忽略每行上限，直接在全矩阵里选全局前 k。
- limits[i] 大于行长度时未做裁剪。
- 累加和可能溢出，需用 long/long long。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public long maxSum(int[][] grid, int[] limits, int k) {
        java.util.List<Integer> candidates = new java.util.ArrayList<>();

        for (int i = 0; i < grid.length; i++) {
            int[] row = grid[i];
            java.util.Arrays.sort(row);
            int take = Math.min(limits[i], row.length);
            for (int t = 0; t < take; t++) {
                candidates.add(row[row.length - 1 - t]);
            }
        }

        candidates.sort(java.util.Collections.reverseOrder());
        long ans = 0L;
        for (int i = 0; i < Math.min(k, candidates.size()); i++) {
            ans += candidates.get(i);
        }
        return ans;
    }
}

import "sort"

func maxSum(grid [][]int, limits []int, k int) int64 {
    candidates := make([]int, 0)

    for i, row := range grid {
        sort.Ints(row)
        take := limits[i]
        if take > len(row) {
            take = len(row)
        }
        for t := 0; t < take; t++ {
            candidates = append(candidates, row[len(row)-1-t])
        }
    }

    sort.Slice(candidates, func(i, j int) bool { return candidates[i] > candidates[j] })
    if k > len(candidates) {
        k = len(candidates)
    }

    var ans int64
    for i := 0; i < k; i++ {
        ans += int64(candidates[i])
    }
    return ans
}

class Solution {
public:
    long long maxSum(vector<vector<int>>& grid, vector<int>& limits, int k) {
        vector<int> candidates;

        for (int i = 0; i < (int)grid.size(); i++) {
            auto& row = grid[i];
            sort(row.begin(), row.end());
            int take = min(limits[i], (int)row.size());
            for (int t = 0; t < take; t++) {
                candidates.push_back(row[(int)row.size() - 1 - t]);
            }
        }

        sort(candidates.begin(), candidates.end(), greater<int>());
        long long ans = 0;
        for (int i = 0; i < min(k, (int)candidates.size()); i++) {
            ans += candidates[i];
        }
        return ans;
    }
};

class Solution:
    def maxSum(self, grid: list[list[int]], limits: list[int], k: int) -> int:
        candidates = []

        for i, row in enumerate(grid):
            row.sort(reverse=True)
            candidates.extend(row[:limits[i]])

        candidates.sort(reverse=True)
        return sum(candidates[:k])

var maxSum = function(grid, limits, k) {
  const candidates = [];

  for (let i = 0; i < grid.length; i++) {
    const row = grid[i].slice().sort((a, b) => b - a);
    const take = Math.min(limits[i], row.length);
    for (let t = 0; t < take; t++) {
      candidates.push(row[t]);
    }
  }

  candidates.sort((a, b) => b - a);
  let ans = 0;
  for (let i = 0; i < Math.min(k, candidates.length); i++) {
    ans += candidates[i];
  }
  return ans;
};