我必須從由“1”和“0”組成的更大正方形中計算正方形中“1”的最大計數，例如：
{0111101010}
{1000010110}
{1001001000}
{1110011001}
{1111110010}
{0011110000}
{0001101000}
{0001101010}
{0110101101}
{0001000001}
每個 0 和 1 也是陣列的一個元素，假設我必須在 6 個元素的邊正方形中找到最多的“1”。我想出了這樣的東西（smallSquareSize = 6）：
for (int i = 0; i < tab.length; i ) {
int count = 0;
for (int j = 0; j < tab.length; j ) {
if(i smallSquareSize <= tab.length && j smallSquareSize <= tab.length) {
for (int x = 0; x < smallSquareSize; x ) {
for (int z = 0; z < smallSquareSize; z ) {
count = count tab[i x][j z];
}
}
}
else break;
if (endCount < count) {
endCount = count;
}
count = 0;
}
}
我在一個大正方形中回圈遍歷每個元素，然后從這里“制作”一個較小的元素。然后我回圈遍歷小元素中的每個元素并計算“1”。
對于上面的示例，答案是 23，較小的正方形從第 3 行第 1 列（從 0,0 開始）開始。
它適用于較小的陣列，但我需要它處理像 5000 個元素的方格。我知道這可能是最愚蠢的解決方案，但我不知道如何擺脫任何 for 回圈以使其運行得更快。
uj5u.com熱心網友回復：
它可能是更好的預先計算的輸入陣列/矩陣的某些部分（例如，在垂直的“條帶”與總和height = smallSquareSize和width = 1），并存盤在另一個陣列這將需要稍微更小的空間，這些子和數：int[][] sub = new int[rows - smallSquareSize 1][cols];
然后計算垂直條帶的總和，cols * (rows - smallSquareSize 1)其基本為 O(N 2 )，子平方和的計算方法與 O(N 2 )類似(rows - smallSquareSize 1) * cols：
public static int maxSum(int smallSquareSize, int[][] arr) {
int rows = arr.length;
int cols = arr[0].length;
int[][] sub = new int[rows - smallSquareSize 1][cols];
for (int c = 0; c < cols; c ) {
int sum = 0;
for (int r = 0; r < smallSquareSize; r ) {
sum = arr[r][c];
}
sub[0][c] = sum;
for (int r = 1; r < sub.length; r ) {
sum = arr[r smallSquareSize - 1][c] - arr[r - 1][c];
sub[r][c] = sum;
}
}
// debug print
System.out.println("Sub-sums:");
for (int r = 0; r < sub.length; r ) {
System.out.println(Arrays.toString(sub[r]));
}
int max = Integer.MIN_VALUE;
for (int r = 0; r < sub.length; r ) {
// calculate subsquare sum
int squareSum = 0;
for (int c = 0; c < smallSquareSize; c ) {
squareSum = sub[r][c];
}
// debug print
System.out.print("s[" r "][" 0 "]=" squareSum);
if (max < squareSum) {
max = squareSum;
}
// subtract previous and add next column to quickly get next subsquare
for (int c = 1; c < cols - smallSquareSize 1; c ) {
squareSum = sub[r][c smallSquareSize - 1] - sub[r][c - 1];
// debug print
System.out.print("\ts[" r "][" c "]=" squareSum);
if (max < squareSum) {
max = squareSum;
}
}
System.out.println();
}
return max;
}
對于給定的輸入，結果如下：
int[][] matrix = {
{0,1,1,1,1,0,1,0,1,0}, {1,0,0,0,0,1,0,1,1,0},
{1,0,0,1,0,0,1,0,0,0}, {1,1,1,0,0,1,1,0,0,1},
{1,1,1,1,1,1,0,0,1,0}, {0,0,1,1,1,1,0,0,0,0},
{0,0,0,1,1,0,1,0,0,0}, {0,0,0,1,1,0,1,0,1,0},
{0,1,1,0,1,0,1,1,0,1}, {0,0,0,1,0,0,0,0,0,1},
};
System.out.println("Max Sum: " maxSum(6, matrix));
帶有除錯訊息的輸出：
Sub-sums:
[4, 3, 4, 4, 3, 4, 3, 1, 3, 1]
[4, 2, 3, 4, 3, 4, 3, 1, 2, 1]
[3, 2, 3, 5, 4, 3, 4, 0, 2, 1]
[2, 3, 4, 4, 5, 3, 4, 1, 2, 2]
[1, 2, 3, 5, 5, 2, 3, 1, 2, 2]
s[0][0]=22 s[0][1]=21 s[0][2]=19 s[0][3]=18 s[0][4]=15
s[1][0]=20 s[1][1]=19 s[1][2]=18 s[1][3]=17 s[1][4]=14
s[2][0]=20 s[2][1]=21 s[2][2]=19 s[2][3]=18 s[2][4]=14
s[3][0]=21 s[3][1]=23 s[3][2]=21 s[3][3]=19 s[3][4]=17
s[4][0]=18 s[4][1]=20 s[4][2]=19 s[4][3]=18 s[4][4]=15
Max Sum: 23
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/322686.html
上一篇：迭代字典并根據其內容計算結果