# LEETCODE 1183. Maximum Number of Ones 解题思路分析

```输入: width = 3, height = 3, sideLength = 2, maxOnes = 1

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]```

```输入: width = 3, height = 3, sideLength = 2, maxOnes = 2

[1,0,1]
[1,0,1]
[1,0,1]```

• `1 <= width, height <= 100`
• `1 <= sideLength <= width, height`
• `0 <= maxOnes <= sideLength * sideLength`

```public int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
int xCount = width / sideLength; // 水平方向能够分割出多少完整子矩阵
int yCount = height / sideLength; // 垂直方向能够分割出多少完整子矩阵
int xRest = width % sideLength; // 水平方向剩余格子
int yRest = height % sideLength; // 垂直方向剩余格子
// 统计每个格子放1后，相应的可以出现多少个1
int[] arr = new int[sideLength*sideLength];
// 循环左上角的子矩阵中每个点
for(int i=0;i<sideLength;i++){
for(int j=0;j<sideLength;j++){
if(i<xRest && j<yRest){
// 对应上图中黄色格子
arr[i*sideLength+j]=(xCount+1) * (yCount+1);
}else if(i<xRest){
// 对应上图中绿色格子
arr[i*sideLength+j]=(xCount+1) * (yCount);
}else if(j < yRest){
// 对应上图中蓝色格子
arr[i*sideLength+j]=(xCount) * (yCount+1);
}else{
// 对应上图中粉色格子
arr[i*sideLength+j]=(xCount) * (yCount);
}
}
}
// 排序数组
Arrays.sort(arr);
int res=0;
// 计算得出数组中前maxOnes大的和即为结果
for(int i=arr.length-1;i>=arr.length-maxOnes;i--){
res+=arr[i];
}
return res;
}```

Runtime: 4 ms, faster than 78.92% of Java online submissions for Maximum Number of Ones.

Memory Usage: 33.6 MB, less than 100.00% of Java online submissions for Maximum Number of Ones.