Question:

Consider a two-dimensional array named matrix of size n x m, where n represents the number of rows and m represents the number of columns. Each cell of the matrix contains an integer value.

Write a Java method countMaxSumSubmatrices(int[][] matrix, int k) that takes in the matrix and an integer k, and returns the number of submatrices in matrix with a sum equal to or greater than k.

The method should have the following signature:

public static int countMaxSumSubmatrices(int[][] matrix, int k)

Input:

• The method accepts two arguments:
  • matrix (0 <= matrix.length <= 100, 0 <= matrix[i].length <= 100): a two-dimensional array of integers.
  • k (1 <= k <= 100): an integer value representing the minimum sum required for a submatrix.

Output:

• The method should return an integer representing the number of submatrices in matrix with a sum equal to or greater than k.

Example:

int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int k = 12;
int result = countMaxSumSubmatrices(matrix, k);

Output

3

Explanation:

In the given example, there are three submatrices with a sum equal to or greater than k=12:

• submatrix1: {{1, 2, 3}, {4, 5, 6}} has a sum of 21.
• submatrix2: {{2, 3}, {5, 6}, {8, 9}} has a sum of 33.
• submatrix3: {{7, 8}, {8, 9}} has a sum of 32.

Therefore, the method should return 3.

Note:

• The submatrices can have any size greater than or equal to 1.

Constraints:

• The input matrix can have at most 100 rows and 100 columns.
• The input matrix can contain negative numbers.
• There can be multiple valid solutions, you should return the count of valid submatrices.