如何证明矩阵三单元格最大总和贪心选择策略的正确性？

Problem Recap #

Given an n×n matrix of non-negative integers, we need to select three cells such that the sum of these cells and their adjacent cells (sharing an edge) is maximized—with overlapping adjacent cells counted only once. The brute-force approach has a time complexity of O(n⁶), while your greedy solution runs in O(n⁴), with the core claim: the cell with the maximum sum of itself plus its adjacent cells must be part of the optimal solution.

Key Definitions #

To formalize the proof, let’s define a few terms:

• For any cell x, let N(x) denote the set of adjacent cells (up, down, left, right, if they exist).
• Let f(x) = sum(x) + sum(N(x)): the total sum of x and all its adjacent cells (the full region covered by x).
• For a set of cells S (here, size 3), let g(S) denote the target sum: the sum of the union of regions {x} ∪ N(x) for all x ∈ S.

Correctness Proof (Exchange Argument) #

We’ll use a proof by contradiction combined with an exchange argument to validate your greedy strategy:

1. Assumption: Let A be the cell with the maximum f(A) value. Suppose there exists an optimal solution S = {x, y, z} where A ∉ S.
2. Construct a New Solution: Replace any cell in S (say, x) with A to get a new solution S' = {A, y, z}. We’ll show g(S') ≥ g(S), which contradicts the assumption that S is optimal.

Step 1: Break Down the Difference Between g(S') and g(S) #

First, split the sums into shared and unique parts:

• Let T = ({y} ∪ N(y)) ∪ ({z} ∪ N(z)): the combined region covered by y and z.
• g(S) = sum(T) + sum( ({x} ∪ N(x)) \ T ): the sum of y and z’s regions, plus the parts of x’s region not covered by y or z.
• g(S') = sum(T) + sum( ({A} ∪ N(A)) \ T ): the sum of y and z’s regions, plus the parts of A’s region not covered by y or z.

The difference between the two sums simplifies to:

g(S') - g(S) = sum( ({A} ∪ N(A)) \ T ) - sum( ({x} ∪ N(x)) \ T )

Step 2: Leverage the Maximality of f(A) #

Since A has the maximum f value, f(A) ≥ f(x). By definition of f:

f(A) = sum({A} ∪ N(A)) = sum( ({A} ∪ N(A)) ∩ T ) + sum( ({A} ∪ N(A)) \ T )
f(x) = sum({x} ∪ N(x)) = sum( ({x} ∪ N(x)) ∩ T ) + sum( ({x} ∪ N(x)) \ T )

Subtracting these equations gives:

0 ≤ f(A) - f(x) = [sum( ({A} ∪ N(A)) ∩ T ) - sum( ({x} ∪ N(x)) ∩ T )] + [sum( ({A} ∪ N(A)) \ T ) - sum( ({x} ∪ N(x)) \ T )]

Step 3: Non-Negativity Guarantees the Difference is Non-Negative #

Since all matrix values are non-negative, we can focus on the unique regions:

• From f(A) ≥ f(x), subtract the overlapping parts with T from both sides:

  sum( ({A} ∪ N(A)) \ T ) ≥ f(x) - sum( ({A} ∪ N(A)) ∩ T )
  

• Substitute f(x) = sum( ({x} ∪ N(x)) ∩ T ) + sum( ({x} ∪ N(x)) \ T ) into the inequality:

  sum( ({A} ∪ N(A)) \ T ) - sum( ({x} ∪ N(x)) \ T ) ≥ sum( ({x} ∪ N(x)) ∩ T ) - sum( ({A} ∪ N(A)) ∩ T )
  

But a more straightforward observation: since f(A) ≥ f(x), the total region covered by A is at least as large as that covered by x. When we remove the parts already covered by y and z, the remaining unique region of A is still at least as large as the remaining unique region of x (because all values are non-negative—we can’t lose sum by replacing x with A).

Thus:

sum( ({A} ∪ N(A)) \ T ) ≥ sum( ({x} ∪ N(x)) \ T )

Which means:

g(S') - g(S) ≥ 0 → g(S') ≥ g(S)

Step 4: Contradiction #

If S is optimal, but we’ve constructed S' with a sum greater than or equal to g(S), this contradicts the assumption that S is strictly optimal. If g(S') = g(S), then S' is also an optimal solution that includes A. Either way, there must exist an optimal solution containing A.

Conclusion #

Using exchange arguments and the non-negativity of matrix values, we’ve proven that the cell with the maximum f(x) value must be part of some optimal solution. This validates the core of your greedy strategy—you can safely select this cell first, then search for the remaining two cells to maximize the total sum.

内容的提问来源于stack exchange，提问作者Chloe