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.

CodePudding user response：

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²), and the sums of the subsquares are calculated similarly for O(N²) (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