Maximum Number of Ones

Similar Problems:

- CheatSheet: LeetCode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #regioninmatrix

Consider a matrix M with dimensions width * height, such that every cell has value 0 or 1, and any square sub-matrix of M of size sideLength * sideLength has at most maxOnes ones.

Return the maximum possible number of ones that the matrix M can have.

Example 1:

Input: width = 3, height = 3, sideLength = 2, maxOnes = 1 Output: 4 Explanation: In a 3*3 matrix, no 2*2 sub-matrix can have more than 1 one. The best solution that has 4 ones is: [1,0,1] [0,0,0] [1,0,1]

Example 2:

Input: width = 3, height = 3, sideLength = 2, maxOnes = 2 Output: 6 Explanation: [1,0,1] [1,0,1] [1,0,1]

Constraints:

- 1 <= width, height <= 100
- 1 <= sideLength <= width, height
- 0 <= maxOnes <= sideLength * sideLength

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

## https://code.dennyzhang.com/maximum-number-of-ones