We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Sum With at Most K Elements

Number: 3764

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an n x m integer matrix grid, an array limits of length n where limits[i] represents the maximum number of elements that can be taken from the iᵗʰ row, and an integer k, the task is to compute the maximum sum you can obtain by selecting at most k elements in total from the grid. For each row, you cannot select more than limits[i] elements.

Key Insights

  • You want the maximum total sum, so picking high-value elements is ideal.
  • For each row, sort the elements in descending order so that the best candidates appear first.
  • Compute prefix sums for each row to quickly calculate the total sum when picking a certain number of highest elements from that row.
  • Use dynamic programming (DP) where dp[j] represents the maximum sum achievable with exactly j elements selected overall.
  • Process each row and update the DP array in reverse order to avoid interfering with the current row’s transition (similar to the knapsack problem).

Space and Time Complexity

Time Complexity: O(n * m log m + n * k * min(m, limits[i])) Space Complexity: O(k), plus O(m) extra space per row when computing sorted order and prefix sums.

Solution

The approach is to treat the problem like a knapsack DP. For each row, sort the row in descending order and compute its prefix sums. For every valid count of elements we might select from the row (up to limits[i]), we update a DP array that tracks the maximum sum achievable with a given total number of selected elements. The key is to update the DP state in reverse (from k downwards) to ensure each row’s choices are only counted once per iteration.

Code Solutions

# Python solution with line-by-line comments

def max_sum_with_k_elements(grid, limits, k):
    n = len(grid)
    # dp[j] represents the maximum sum achievable with exactly j items selected
    dp = [-float('inf')] * (k + 1)
    dp[0] = 0

    # Process each row separately
    for row_idx in range(n):
        # Sort the row in descending order to get largest values first
        sorted_row = sorted(grid[row_idx], reverse=True)
        # Determine maximum items we can take from this row
        limit = min(limits[row_idx], len(sorted_row))
        # Calculate prefix sums for the row: prefix_sums[i] is the sum of first i elements
        prefix_sums = [0] * (limit + 1)
        for i in range(1, limit + 1):
            prefix_sums[i] = prefix_sums[i-1] + sorted_row[i-1]
        
        # Update dp array in reverse order
        for j in range(k, -1, -1):
            # Try all options: taking count elements from current row
            for count in range(1, limit + 1):
                if j - count >= 0:
                    dp[j] = max(dp[j], dp[j - count] + prefix_sums[count])
    # Maximum sum with at most k elements is the maximum dp value from 0 to k
    return max(dp)

# Example usage:
grid1 = [[1,2],[3,4]]
limits1 = [1,2]
k1 = 2
print(max_sum_with_k_elements(grid1, limits1, k1))  # Expected output: 7

grid2 = [[5,3,7],[8,2,6]]
limits2 = [2,2]
k2 = 3
print(max_sum_with_k_elements(grid2, limits2, k2))  # Expected output: 21
← Back to All Questions