Test2

public static int maxSumTwoSubgrids(int[][] grid) {         int N = grid.length;         int maxSum = Integer.MIN_VALUE;           // Precompute the sums of all possible subgrids         int[][] subgridSums = new int[N + 1][N + 1];         for (int i = 0; i < N; i++) {             for (int j = 0; j < N; j++) {                 subgridSums[i + 1][j + 1] = grid[i][j] + subgridSums[i][j + 1] + subgridSums[i + 1][j] - subgridSums[i][j];             }         }           // Helper function to get sum of subgrid         int getSum(int x1, int y1, int x2, int y2) {             return subgridSums[x2 + 1][y2 + 1] - subgridSums[x1][y2 + 1] - subgridSums[x2 + 1][y1] + subgridSums[x1][y1];         }           // Iterate over all possible sizes of the first subgrid         for (int size1 = 1; size1 <= N; size1++) {             for (int x1 = 0; x1 <= N - size1; x1++) {                 for (int y1 = 0; y1 <= N - size1; y1++) {                     int sum1 = getSum(x1, y1, x1 + size1 - 1, y1 + size1 - 1);                       // Mark rows and columns used by the first subgrid                     Set<Integer> rowsUsed = new HashSet<>();                     Set<Integer> colsUsed = new HashSet<>();                     for (int i = x1; i < x1 + size1; i++) rowsUsed.add(i);                     for (int j = y1; j < y1 + size1; j++) colsUsed.add(j);                       // Iterate over all possible sizes of the second subgrid                     for (int size2 = 1; size2 <= N; size2++) {                         for (int x2 = 0; x2 <= N - size2; x2++) {                             for (int y2 = 0; y2 <= N - size2; y2++) {                                 // Check if the second subgrid intersects with the first                                 boolean intersects = false;                                 for (int i = x2; i < x2 + size2; i++) {                                     if (rowsUsed.contains(i)) {                                         intersects = true;                                         break;                                     }                                 }                                 if (!intersects) {                                     for (int j = y2; j < y2 + size2; j++) {                                         if (colsUsed.contains(j)) {                                             intersects = true;                                             break;                                         }                                     }                                 }                                 if (intersects) continue;                                   int sum2 = getSum(x2, y2, x2 + size2 - 1, y2 + size2 - 1);                                 maxSum = Math.max(maxSum, sum1 + sum2);                             }                         }                     }                 }             }         }           return maxSum;     }   --------------- V2 private static int getSum(int[][] subgridSums, int x1, int y1, int x2, int y2) {         return subgridSums[x2 + 1][y2 + 1] - subgridSums[x1][y2 + 1] - subgridSums[x2 + 1][y1] + subgridSums[x1][y1];     } ------------------- V3 public static int maxSumTwoSubgrids(int[][] grid) {         int N = grid.length;         int maxSum = Integer.MIN_VALUE;         // Precompute the sums of all possible subgrids         int[][] subgridSums = new int[N + 1][N + 1];         for (int i = 0; i < N; i++) {             for (int j = 0; j < N; j++) {                 subgridSums[i + 1][j + 1] = grid[i][j] + subgridSums[i][j + 1] + subgridSums[i + 1][j] - subgridSums[i][j];             }         }         // Iterate over all possible sizes of the first subgrid         for (int size1 = 1; size1 <= N; size1++) {             for (int x1 = 0; x1 <= N - size1; x1++) {                 for (int y1 = 0; y1 <= N - size1; y1++) {                     int sum1 = getSum(subgridSums, x1, y1, x1 + size1 - 1, y1 + size1 - 1);                     // Mark rows and columns used by the first subgrid                     Set<Integer> rowsUsed = new HashSet<>();                     Set<Integer> colsUsed = new HashSet<>();                     for (int i = x1; i < x1 + size1; i++) rowsUsed.add(i);                     for (int j = y1; j < y1 + size1; j++) colsUsed.add(j);                     // Iterate over all possible sizes of the second subgrid                     for (int size2 = 1; size2 <= N; size2++) {                         for (int x2 = 0; x2 <= N - size2; x2++) {                             for (int y2 = 0; y2 <= N - size2; y2++) {                                 // Check if the second subgrid intersects with the first                                 boolean intersects = false;                                 for (int i = x2; i < x2 + size2; i++) {                                     if (rowsUsed.contains(i)) {                                         intersects = true;                                         break;                                     }                                 }                                 if (!intersects) {                                     for (int j = y2; j < y2 + size2; j++) {                                         if (colsUsed.contains(j)) {                                             intersects = true;                                             break;                                         }                                     }                                 }                                 if (intersects) continue;                                 int sum2 = getSum(subgridSums, x2, y2, x2 + size2 - 1, y2 + size2 - 1);                                 maxSum = Math.max(maxSum, sum1 + sum2);                             }                         }                     }                 }             }         }         return maxSum;     }     private static int getSum(int[][] subgridSums, int x1, int y1, int x2, int y2) {         return subgridSums[x2 + 1][y2 + 1] - subgridSums[x1][y2 + 1] - subgridSums[x2 + 1][y1] + subgridSums[x1][y1];     }