Finding the maximum sum square submatrix in a 2D array.
Here’s a Java code that solves the problem of finding the maximum sum square submatrix in a 2D array:
public class MaxSumSquareSubmatrix {
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
int submatrixSize = 2;
int maxSum = findMaxSumSquareSubmatrix(matrix, submatrixSize);
System.out.println("Maximum sum of a " + submatrixSize + "x" + submatrixSize + " submatrix: " + maxSum);
}
public static int findMaxSumSquareSubmatrix(int[][] matrix, int submatrixSize) {
int rows = matrix.length;
int cols = matrix[0].length;
// Calculate prefix sum matrix
int[][] prefixSum = new int[rows + 1][cols + 1];
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
prefixSum[i][j] = matrix[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
}
}
int maxSum = Integer.MIN_VALUE;
// Find maximum sum submatrix
for (int i = submatrixSize; i <= rows; i++) {
for (int j = submatrixSize; j <= cols; j++) {
int currentSum = prefixSum[i][j] - prefixSum[i - submatrixSize][j] - prefixSum[i][j - submatrixSize] + prefixSum[i - submatrixSize][j - submatrixSize];
maxSum = Math.max(maxSum, currentSum);
}
}
return maxSum;
}
}
In this code, the `findMaxSumSquareSubmatrix` method takes a 2D matrix and the size of the submatrix as input and returns the maximum sum of a square submatrix of the given size. It uses a dynamic programming approach to calculate the prefix sum matrix, which allows us to efficiently compute the sum of any submatrix in constant time. Then, it iterates through all possible submatrices of the given size and updates the `maxSum` variable whenever a higher sum is found. Finally, it returns the maximum sum.
In the provided example, the matrix is initialized with some values, and the submatrix size is set to 2. The code calculates the maximum sum of a 2×2 submatrix in the matrix and prints the result. You can modify the matrix values and the submatrix size to test the code with different inputs.