Maximum Sum With at Most K Elements

1. Preprocessing:
   • For each row i in the grid, sort it in descending order.
   • For each row i, compute its prefix sums. Let P[i][j] be the sum of the j largest elements in row i. P[i][0] is 0.
2. Dynamic Programming Setup:
   • Create a 1D DP array, dp, of size k + 1, initialized to zeros. dp[j] will store the maximum sum achievable using exactly j elements from the rows processed so far.
3. DP Iteration:
   • Iterate through each row i from 0 to n-1.
   • For each row, update the dp array. Iterate j from k down to 1.
   • For each j, iterate through the number of elements c to take from the current row i, where 1 <= c <= limits[i] and c <= j.
   • The transition is: dp[j] = max(dp[j], dp[j - c] + P[i][c]).
4. Result:
   • Since we can take at most k elements and all element values are non-negative, the maximum sum will be the largest value in the dp array after processing all rows. The answer is max(dp[0], dp[1], ..., dp[k]).

First, we preprocess the data to make the DP transitions efficient. For each row, we sort it in descending order to easily access the largest elements. Then, we compute the prefix sums for each sorted row. prefixSums[i][c] will store the sum of the c largest elements of row i.

The DP state dp[j] represents the maximum sum using exactly j elements. We use a 1D array for space optimization. We iterate through each row i and for each row, we update the dp array. We iterate the total elements j from k down to 1 (to avoid using elements from the same row multiple times in a single update step). For each j, we consider taking c elements from the current row i, where c ranges from 1 to limits[i]. The new dp[j] will be the maximum of its current value and dp[j-c] + prefixSums[i][c], which represents the sum from previous rows plus the sum from taking c elements from the current row.

After iterating through all the rows, the dp array holds the maximum sums for taking exactly 0, 1, ..., k elements. The final answer is the maximum value in this dp array.

1class Solution {2    public long maximumSum(int[][] grid, int[] limits, int k) {3        int n = grid.length;4        int m = grid[0].length;5 6        // 1. Preprocessing: Sort rows and compute prefix sums7        long[][] prefixSums = new long[n][m + 1];8        for (int i = 0; i < n; i++) {9            Arrays.sort(grid[i]);10            // Reverse for descending order11            for (int l = 0, r = m - 1; l < r; l++, r--) {12                int temp = grid[i][l];13                grid[i][l] = grid[i][r];14                grid[i][r] = temp;15            }16            17            prefixSums[i][0] = 0;18            for (int j = 0; j < m; j++) {19                prefixSums[i][j + 1] = prefixSums[i][j] + grid[i][j];20            }21        }22 23        // 2. DP with space optimization24        long[] dp = new long[k + 1];25 26        for (int i = 0; i < n; i++) {27            for (int j = k; j >= 1; j--) {28                for (int c = 1; c <= Math.min(j, limits[i]); c++) {29                    if (j - c >= 0) {30                        dp[j] = Math.max(dp[j], dp[j - c] + prefixSums[i][c]);31                    }32                }33            }34        }35 36        // 3. Result is the max value in the dp array37        long maxSum = 0;38        for (long sum : dp) {39            maxSum = Math.max(maxSum, sum);40        }41        return maxSum;42    }43}

1. Preprocessing:
   • Sort each row of the grid in descending order. This allows us to access the largest elements of each row sequentially.
2. Setup Max-Heap:
   • Create a max-heap (Priority Queue) to store entries of {value, rowIndex}.
   • Initialize the heap by adding the largest element from each row i (i.e., grid[i][0]), provided limits[i] > 0 and the row is not empty.
3. Greedy Selection:
   • Initialize totalSum = 0 and an array rowIndices to track the index of the next element to consider from each row.
   • Loop up to k times or until the heap is empty:
     • Extract the element with the maximum value from the heap. Let this be {value, row}.
     • Add value to totalSum.
     • Increment the index for the row (rowIndices[row]++).
     • If there are more elements to consider in that row (i.e., rowIndices[row] < m) and the row's limit has not been reached (rowIndices[row] < limits[row]), add the next largest element from that row (grid[row][rowIndices[row]]) to the heap.
4. Result:
   • Return totalSum.

The core idea is that to get the maximum sum, we should always pick the largest available number. The constraints are that we can pick at most k numbers in total, and from each row i, at most limits[i] numbers.

First, we sort each row in descending order. This makes it easy to find the 1st, 2nd, 3rd, etc., largest elements of any row.

We use a max-heap to keep track of the current best candidate from each row. Initially, we populate the heap with the largest element of each row. Then, we repeat k times: extract the max element from the heap. Suppose this element came from row r. We add its value to our total sum. Then, we offer the next largest element from row r to the heap, but only if we haven't exhausted the elements in row r or exceeded the limits[r] for that row. This process ensures that at every step, we are picking the globally largest element available that satisfies all constraints.

This greedy strategy is optimal because of an exchange argument: if there were a better solution, it must differ from the greedy one at some step. At the first differing step, the greedy algorithm chose an element g while the optimal solution chose o. By the greedy choice property, g >= o. We can swap o with g in the optimal solution to get an equally good or better solution, moving it closer to the greedy solution. Repeating this proves the greedy solution is optimal.

1class Solution {2    public long maximumSum(int[][] grid, int[] limits, int k) {3        int n = grid.length;4        int m = grid[0].length;5 6        // 1. Sort each row in descending order7        for (int i = 0; i < n; i++) {8            Arrays.sort(grid[i]);9            for (int l = 0, r = m - 1; l < r; l++, r--) {10                int temp = grid[i][l];11                grid[i][l] = grid[i][r];12                grid[i][r] = temp;13            }14        }15 16        // Max-heap to store {value, row_index}17        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);18        19        // 2. Initialize heap with the largest element from each row20        for (int i = 0; i < n; i++) {21            if (limits[i] > 0 && m > 0) {22                pq.offer(new int[]{grid[i][0], i});23            }24        }25 26        long totalSum = 0;27        int[] rowIndices = new int[n]; // Tracks elements taken from each row28 29        // 3. Greedily pick up to k largest elements30        for (int i = 0; i < k && !pq.isEmpty(); i++) {31            int[] top = pq.poll();32            int value = top[0];33            int row = top[1];34 35            totalSum += value;36            rowIndices[row]++;37            38            // If there are more elements in the row and we haven't hit the limit,39            // offer the next element from that row to the heap.40            if (rowIndices[row] < m && rowIndices[row] < limits[row]) {41                pq.offer(new int[]{grid[row][rowIndices[row]], row});42            }43        }44 45        return totalSum;46    }47}

1. Preprocessing:
   • Sort each row of the grid in descending order: O(n*m*log m).
   • Compute prefix sums for each sorted row to quickly find the sum of the top x elements: O(n*m).
2. Binary Search for Threshold:
   • The key insight is that the number of elements we can pick is monotonic with respect to a minimum value threshold. If we can pick C elements with value >= T, we can also pick at least C elements with value >= T-1.
   • We can binary search for the optimal threshold value T. This T will be the value of the k-th element we pick (or 0 if we pick fewer than k elements).
   • The search space for T is [0, 10^5 + 1].
   • For each mid value in the binary search, we have a check(mid) function that counts how many elements with value >= mid can be picked across all rows while respecting the limits array. This check can be done in O(n*log m) by using binary search on each sorted row.
   • We want to find the largest T such that check(T) >= k.
3. Calculate Final Sum:
   • Once the optimal threshold T is found, we can calculate the final sum.
   • First, sum up all elements that are strictly greater than T, respecting each row's limit. This can be done in O(n*log m) using the precomputed prefix sums.
   • Let the count of these elements be elementsCount.
   • We need to pick k - elementsCount more elements. Since T is our threshold, all these remaining elements will have the value T.
   • The final sum is (sum of elements > T) + (k - elementsCount) * T.
4. Result:
   • Return the calculated total sum.

This approach hinges on binary searching for the value of the k-th largest element we select. Let's call this threshold T.

First, we preprocess by sorting each row in descending order and calculating their prefix sums. This allows for efficient queries later.

We then perform a binary search on the possible values of elements, from 0 to 100001. For a given value mid in our search, we define a function check(mid) that determines if it's possible to select at least k elements from the grid with values >= mid, while respecting the limits for each row. check(mid) works by iterating through each row, finding how many elements are >= mid (using binary search on the sorted row), taking the minimum of that count and limits[i], and summing these counts up. If the total count is >= k, check(mid) returns true.

The main binary search aims to find the largest value T for which check(T) is true. This T is the minimum value an element can have to be included in our top k choices.

To calculate the final sum, we first take all elements strictly greater than T. For each row, we find how many elements are > T, take the minimum of this count and limits[i], and use our prefix sum array to add their sum to our totalSum. We also count how many elements we've taken so far (elementsCount). Finally, we need to take k - elementsCount more elements. By the definition of our threshold T, all these must have the value T. So, we add (k - elementsCount) * T to our totalSum.

1class Solution {2    public long maximumSum(int[][] grid, int[] limits, int k) {3        int n = grid.length;4        int m = grid[0].length;5 6        // 1. Preprocessing7        for (int i = 0; i < n; i++) {8            Arrays.sort(grid[i]);9            for (int l = 0, r = m - 1; l < r; l++, r--) {10                int temp = grid[i][l];11                grid[i][l] = grid[i][r];12                grid[i][r] = temp;13            }14        }15        long[][] prefixSums = new long[n][m + 1];16        for (int i = 0; i < n; i++) {17            for (int j = 0; j < m; j++) {18                prefixSums[i][j + 1] = prefixSums[i][j] + grid[i][j];19            }20        }21 22        // 2. Binary search for the threshold value T23        int low = 0, high = 100001, T = 0;24        while (low <= high) {25            int mid = low + (high - low) / 2;26            if (canTakeAtLeastK(grid, limits, k, mid)) {27                T = mid;28                low = mid + 1;29            } else {30                high = mid - 1;31            }32        }33 34        // 3. Calculate final sum35        long totalSum = 0;36        int elementsCount = 0;37        for (int i = 0; i < n; i++) {38            int countGreaterThanT = countGreater(grid[i], T);39            int numToTake = Math.min(countGreaterThanT, limits[i]);40            totalSum += prefixSums[i][numToTake];41            elementsCount += numToTake;42        }43 44        if (elementsCount < k) {45            totalSum += (long)(k - elementsCount) * T;46        }47 48        return totalSum;49    }50 51    private boolean canTakeAtLeastK(int[][] grid, int[] limits, int k, int threshold) {52        long count = 0;53        for (int i = 0; i < grid.length; i++) {54            count += Math.min(countGreaterOrEqual(grid[i], threshold), limits[i]);55            if (count >= k) return true;56        }57        return false;58    }59 60    private int countGreaterOrEqual(int[] row, int val) {61        int l = 0, r = row.length - 1, ans = row.length;62        while (l <= r) {63            int mid = l + (r - l) / 2;64            if (row[mid] < val) {65                ans = mid;66                r = mid - 1;67            } else { // row[mid] >= val68                l = mid + 1;69            }70        }71        return ans;72    }73 74    private int countGreater(int[] row, int val) {75        int l = 0, r = row.length - 1, ans = row.length;76        while (l <= r) {77            int mid = l + (r - l) / 2;78            if (row[mid] <= val) {79                ans = mid;80                r = mid - 1;81            } else { // row[mid] > val82                l = mid + 1;83            }84        }85        return ans;86    }87}