Untitled
unknown
plain_text
a month ago
1.9 kB
2
Indexable
import java.util.HashMap; public class LargestZeroSumSubmatrix { public static int largestZeroSumSubmatrix(int[][] matrix) { int n = matrix.length, m = matrix[0].length; int maxArea = 0; // Fix the left column boundary for (int c1 = 0; c1 < m; c1++) { int[] rowSum = new int[n]; // Row-wise collapsed sum // Expand the right column boundary for (int c2 = c1; c2 < m; c2++) { // Compute the sum for each row within column boundaries c1 to c2 for (int row = 0; row < n; row++) { rowSum[row] += matrix[row][c2]; } // Find the max height (rows) for sum 0 int height = largestSubarrayWithSumZero(rowSum); int width = c2 - c1 + 1; maxArea = Math.max(maxArea, width * height); } } return maxArea; } // Function to find the longest subarray with sum 0 private static int largestSubarrayWithSumZero(int[] arr) { HashMap<Integer, Integer> prefixMap = new HashMap<>(); int prefixSum = 0, maxLen = 0; for (int i = 0; i < arr.length; i++) { prefixSum += arr[i]; if (prefixSum == 0) { maxLen = i + 1; } if (prefixMap.containsKey(prefixSum)) { maxLen = Math.max(maxLen, i - prefixMap.get(prefixSum)); } else { prefixMap.put(prefixSum, i); } } return maxLen; } public static void main(String[] args) { int[][] matrix = { {1, 2, -3, 4}, {-3, -1, 2, 1}, {2, 3, -4, -2} }; System.out.println("Largest Zero Sum Submatrix Area: " + largestZeroSumSubmatrix(matrix)); } }
Editor is loading...
Leave a Comment