Grid Elimination: Remove Rows and Columns From a Matrix to Maximize Remaining Sum

Question

## Problem

You are given an `m x n` integer matrix. You may eliminate at most `k` rows and at most `k` columns. After elimination, the score is the sum of all remaining cells. Maximize the score.

```python
def max_score(matrix: list[list[int]], k: int) -> int:
    pass
```

**Example:**
```
matrix = [[-1,  2,  3],
          [ 4, -5,  6],
          [ 7,  8, -9]]
k = 1

Eliminate row 0 (-1+2+3=4, smallest row sum) and column 2 (3+6-9=0):
  Remaining: [[4,-5],[7,8]] -> sum = 14
Or eliminate col 1 and row 2: ...
Find the combination maximizing the total.

Output: (depends on best elimination choice)
```

## Follow-ups

1. For small k, is brute force (try all C(m,k)*C(n,k) combinations) feasible? When does it break?
2. Is greedy (always eliminate the row/column with the smallest sum) always optimal? Prove or give a counterexample.
3. If you can eliminate exactly k rows AND exactly k columns (not at most), does the problem change?
4. How would you solve this for k up to min(m,n)/2 efficiently?

Grid Elimination: Remove Rows and Columns From a Matrix to Maximize Remaining Sum

Question Details

Full Details

Topics

More from Roblox