Maximize the total binary score of a matrix by optionally flipping rows and columns.
You are given an binary matrix. The score of a row is the value of its bits interpreted as a binary number, with the leftmost column as the most significant bit.
You may flip any row any number of times and any column any number of times. Flipping a row or column toggles every bit in that row or column.
Return the maximum possible sum of the row scores after performing any sequence of flips.
The goal is to choose row and column flips so that the matrix represents the largest possible total binary value.
Input Format
- An integer matrix
gridof sizem x n. - Each cell contains either
0or1. - A row flip toggles all values in one row.
- A column flip toggles all values in one column.
Output Format
- Return a single integer: the maximum total score achievable after any number of row and column flips.
Constraints
grid[i][j] ∈ {0, 1}- The matrix is non-empty
- The result fits in a standard 64-bit signed integer in typical interview settings
Example 1
Input
grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output
39
Explanation
Flip the first row to make the leading bits all 1 where needed, then choose column flips to maximize each column's contribution. One optimal final matrix is [[1,1,1,1],[1,0,1,0],[1,1,0,0]], whose row values are 15, 10, and 12, totaling 37? But a better optimal configuration is obtained by flipping the second column as well, giving total 39.
Example 2
Input
grid = [[0]]
Output
1
Explanation
Flip the only row or the only column to make the single bit 1. The score is then 1.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.