I have to count what’s the biggest count of “1” in a square from a bigger square made of “1” and “0”, like:

{0111101010} {1000010110} {1001001000} {1110011001} {1111110010} {0011110000} {0001101000} {0001101010} {0110101101} {0001000001}

Each 0 and 1 is also an element of the array, and let’s say I have to find the most “1” in a 6 elements side square. I came up with something like this (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; } }

I am looping through every single element in a big square and from here I ‘make’ a smaller one. Then I am looping through every element in the small one and count the “1”.

For the example above, the answer is 23 and smaller square starts at row 3 column 1 (starting at 0,0).

It works well for smaller arrays, but I need it to work on like 5000 elements side squares. I know that this is probably the dumbest solution possible, but I have no idea how to get rid of any of those for loops to make it run faster.

## Answer

It may be better to pre-calculate some parts of the input array/matrix (e.g. the sums in the vertical “strips” with `height = smallSquareSize`

and `width = 1`

) and store these sub-sums in another array which would require slightly less space: `int[][] sub = new int[rows - smallSquareSize + 1][cols];`

Then the sums for the vertical strips are counted for `cols * (rows - smallSquareSize + 1)`

which is basically O(N^{2}), and the sums of the subsquares are calculated similarly for 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; }

For the given input the results are as follows:

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));

Output with debug messages:

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