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];
}