1975. Maximum Matrix Sum
Approach
Sum absolute values; if odd number of negatives subtract 2 * minimum absolute value.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
Matrix problems often involve BFS/DFS flood fill, dynamic programming on 2D grids, or spiral/diagonal traversal. For row × column DP, break it into 1D sub-problems column by column. Common pitfalls: boundary checks and modifying the input matrix in-place.
// Approach: Sum absolute values; if odd number of negatives subtract 2 * minimum absolute value.
// Time: O(mn) Space: O(1)
public class Solution
{
public long MaxMatrixSum(int[][] matrix)
{
long absSum = 0;
int minAbs = int.MaxValue;
// 0 := even number of negatives
// 1 := odd number of negatives
int oddNeg = 0;
foreach (int[] row in matrix)
{
foreach (int num in row)
{
absSum += Math.Abs(num);
minAbs = Math.Min(minAbs, Math.Abs(num));
if (num < 0)
oddNeg ^= 1;
}
}
return absSum - oddNeg * minAbs * 2;
}
}