Given a 2D array, find the maximum sum submatrix in it.
Input: int[][] matrix = new int[][]{{2, 4, -3, -8, -11}, {-7, -6, 9, 1, 3}, {5, 10, 12, 7, 8}, {-9, -2, 3, 6, -2}}; Output: 49 Explanation: The maximum sum submatrix is formed by the cells from row 1 to row 3, columns 1 to column 4, formed by the ecuation: - 6 + 9 + 1 + 3 +10 + 12 + 7 + 8 -2 + 3 + 6 -2 = 49. |
Solution:
1. private static int maximumSumRectangle(int[][] matrix) { 2. int rows = matrix.length; 3. int columns = matrix[0].length; 4. int[][] intermediarySums = new int[rows + 1][columns]; 5. 6. for (int i = 0; i < rows; i++) { 7. for (int j = 0; j < columns; j++) { 8. intermediarySums[i + 1][j] = intermediarySums[i][j] + matrix[i][j]; 9. } 10. } 11. 12. int maxSum = -1; 13. int minSum = Integer.MIN_VALUE; 14. for (int i = 0; i < rows; i++) { 15. for (int row = i; row < rows; row++) { 16. int sum = 0; 17. for (int column = 0; column < columns; column++) { 18. sum += intermediarySums[row + 1][column] - intermediarySums[i][column]; 19. if (sum < 0) { 20. if (minSum < sum) { 21. minSum = sum; 22. } 23. sum = 0; 24. } else if (maxSum < sum) { 25. maxSum = sum; 26. } 27. } 28. } 29. } 30. return maxSum == -1 ? minSum : maxSum; 31. } 32.