3764. Maximum Sum With At Most K Elements¶

3764. Maximum Sum With at Most K Elements

Medium

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

The number of elements taken from the i^th row of grid does not exceed limits[i].

Return the maximum sum.

Example 1:

Input: grid = [[1,2],[3,4]], limits = [1,2], k = 2

Output: 7

Explanation:

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

Example 2:

Input: grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3

Output: 21

Explanation:

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

Constraints:

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

Solution¶

class Solution {
    private long dp[][];
    public long maxSum(int[][] grid, int[] limits, int k) {
        int n = grid.length, m = grid[0].length;
        ArrayList<Integer> arr = new ArrayList<>();
        ArrayList<ArrayList<Integer>> elements = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> r = new ArrayList<>();
            for (int j = 0; j < m; j++) r.add(grid[i][j]);
            Collections.sort(r);
            Collections.reverse(r);
            ArrayList<Integer> r1 = new ArrayList<>();
            for (int ele : r) if (r1.size() < limits[i]) r1.add(ele);
            elements.add(new ArrayList<>(r1));
        }
        for (ArrayList<Integer> x : elements)  for (int ele : x) arr.add(ele);
        Collections.sort(arr);
        Collections.reverse(arr);
        long ans = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (k == 0) break;
            ans += arr.get(i);
            k--;
        }
        return ans;
    }
    private long solve(int ind, int k, ArrayList<Integer> arr) {
        if (ind >= arr.size()) return 0;
        if (dp[ind][k] != -1) return dp[ind][k];
        long op1 = Integer.MIN_VALUE / 10, op2 = Integer.MIN_VALUE / 10;
        if (k > 0) op1 = arr.get(ind) + solve(ind + 1, k - 1, arr);
        op2 = solve(ind + 1, k, arr);
        return dp[ind][k] = Math.max(op1, op2);
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]