Maximum Sum Submatrix II - Java Solution and Time Complexity Analysis

Given a m x n grid filled with integers, find the submatrix with maximum sum among all submatrices.

Example:

Input:
[
  [ 1,  -9, -10,  1],
  [-1,  10,  10,  1],
  [ 0,   9,   9, -9],
  [-1,  -1,  -1, -1]
]
Output: 38
Explanation: Submatrix [[10, 10], [9, 9]]

Understanding the Problem

The core challenge of this problem is to identify the submatrix within a given m x n grid that has the maximum sum. This problem is significant in various applications such as image processing, financial analysis, and any domain where data is represented in a matrix form. A common pitfall is to assume that the submatrix must be of a fixed size, but it can be of any size from 1x1 to mxn.

Approach

To solve this problem, we can break it down into the following steps:

Calculate the prefix sum for each row to simplify the sum calculation of any submatrix.
Use a nested loop to consider all possible pairs of rows.
For each pair of rows, use a 1D array to store the sum of elements between these rows for each column.
Apply Kadane's algorithm on this 1D array to find the maximum sum subarray, which corresponds to the maximum sum submatrix for the current pair of rows.

This approach ensures that we efficiently find the maximum sum submatrix without having to check every possible submatrix explicitly.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Compute the prefix sum for each row.
Iterate over all pairs of rows (i, j).
For each pair of rows, create a 1D array that stores the sum of elements between these rows for each column.
Apply Kadane's algorithm on this 1D array to find the maximum sum subarray.
Keep track of the maximum sum found during these iterations.

Code Implementation

import java.util.*;

public class MaximumSumSubmatrix {
    public static int maxSumSubmatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int maxSum = Integer.MIN_VALUE;

        // Compute prefix sums for each row
        int[][] prefixSum = new int[m][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i][j + 1] = prefixSum[i][j] + matrix[i][j];
            }
        }

        // Iterate over all pairs of rows
        for (int i = 0; i < m; i++) {
            for (int j = i; j < m; j++) {
                // Create a 1D array to store the sum of elements between rows i and j for each column
                int[] sums = new int[n];
                for (int k = 0; k < n; k++) {
                    sums[k] = prefixSum[j][k + 1] - prefixSum[i][k + 1];
                }

                // Apply Kadane's algorithm to find the maximum sum subarray
                int currentMax = kadane(sums);
                maxSum = Math.max(maxSum, currentMax);
            }
        }

        return maxSum;
    }

    // Helper function to apply Kadane's algorithm
    private static int kadane(int[] array) {
        int maxEndingHere = array[0];
        int maxSoFar = array[0];
        for (int i = 1; i < array.length; i++) {
            maxEndingHere = Math.max(array[i], maxEndingHere + array[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, -9, -10, 1},
            {-1, 10, 10, 1},
            {0, 9, 9, -9},
            {-1, -1, -1, -1}
        };
        System.out.println(maxSumSubmatrix(matrix)); // Output: 38
    }
}

Complexity Analysis

The time complexity of this approach is O(m^2 * n), where m is the number of rows and n is the number of columns. This is because we iterate over all pairs of rows and for each pair, we apply Kadane's algorithm which takes O(n) time. The space complexity is O(m * n) for storing the prefix sums.

Edge Cases

Potential edge cases include:

All elements are negative: The algorithm should still return the maximum (least negative) sum.
Single row or single column matrix: The algorithm should handle these cases correctly.
Matrix with zeroes: The algorithm should correctly identify submatrices with zero sum if they are the maximum.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with small matrices.
Cases with all negative numbers.
Cases with mixed positive, negative, and zero values.
Large matrices to test performance.

Thinking and Problem-Solving Tips

When approaching such problems, it is crucial to break down the problem into smaller parts and think about how to simplify the calculations. Using prefix sums and Kadane's algorithm are examples of such simplifications. Practice similar problems to get a better understanding of dynamic programming and optimization techniques.

Conclusion

In this blog post, we discussed how to find the maximum sum submatrix in a given m x n grid. We explored the problem, understood the challenges, and developed an efficient solution using prefix sums and Kadane's algorithm. By analyzing the complexity and considering edge cases, we ensured that our solution is robust and efficient.