LC: 1183. Maximum Number of Ones - spiralgo/algorithms GitHub Wiki

1183. Maximum Number of Ones:

The Essence:

• We can imagine a square at the top left of the matrix.
• We can assume that the matrix itself is a product of copying this square multiple times and cutting the edges according to the matrix size.
• Then we can assign an id for each tile of the square. (Just like we have done in https://github.com/spiralgo/algorithms/pull/329 with getNodeId())

Details:

We need to count how many times each tile id could repeat (if the tile would have been selected to set 1 in it) Then we select top n (=maxOnes) tiles that repeat most in order to get the maximum benefit. (We could also use a PQ instead of sorting the array.)

A more detailed explanation with image and the implementation: https://github.com/spiralgo/algorithms/pull/336