This problem can be solved using Kadane’s Algorithm.
We start by taking an empty array of zeros of size of the number of rows of input matrix.
We move from left to right columns and calculate max for every column and update up, down, left, right accordingly.
Input matrix mxn
Time = O(m*n*n)
Space = O(m)
package algos; import java.util.HashMap; class solution { public solution() { } public HashMapgetMaxSum(int[] arr) { int max = arr[0], start = 0, end = 0, mstart = 0, mend = 0, currmax = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > arr[i] + currmax) { currmax = arr[i]; start = i; end = i; } else { currmax = currmax + arr[i]; end = i; } if (currmax > max) { max = currmax; mstart = start; mend = end; } } HashMap result = new HashMap (); result.put("up", mstart); result.put("down", mend); result.put("max", max); return result; } public HashMap getMaxSubArray(int[][] matrix) { int max = matrix[0][0], left = 0, right = 0, up = 0, down = 0; int[] rowArray = new int[matrix.length]; for (int cl = 0; cl < matrix[0].length; cl++) { for (int i = 0; i < matrix.length; i++) { rowArray[i] = 0; } for (int cr = cl; cr < matrix[0].length; cr++) { for (int row = 0; row < matrix.length; row++) { rowArray[row] += matrix[row][cr]; } HashMap currentSet = getMaxSum(rowArray); if (currentSet.get("max") > max) { max = currentSet.get("max"); up = currentSet.get("up"); down = currentSet.get("down"); left = cl; right = cr; } } } HashMap result = new HashMap (); result.put("up", up); result.put("down", down); result.put("left", left); result.put("right", right); result.put("max", max); return result; } } public class kadanes { public static void main(String[] args) { solution sol = new solution(); int[][] matrix = { { -2, -2, -2 }, { 2, 2, 2 }, { -2, -2, -2 } }; HashMap result = sol.getMaxSubArray(matrix); System.out.println("max:" + result.get("max") + " up:" + result.get("up") + " down:" + result.get("down") + " left:" + result.get("left") + " right:" + result.get("right")); } }
Output
max:6 up:1 down:1 left:0 right:2