Given a matrix which contains positive and negative integers. Find the submatrix which has the maximum sum.
There are total O(n^2) row range and O(n^2) column range. So total O(n^4) sub matrix. To find the sum of any sub matrix we need to do a O(n^2) operation. So the brute force algorithm will have a complexity of O(n^6).
We will create a same sized matrix to keep the vertical sum of the original matrix. For example verticalSum[i,j]=arr[0,j]+arr[1,j]+...+arr[i,j]. Now we will take the row range and move from left to right to find the maximum sum. There are O(n^2) row range possible. Row range will be a range from rowStart to rowEnd. Both of these variables can vary from 1 to n. So there are O(n^2) rowRange possible. For any starting row we start with one row and move from left to right. Then we take 2 rows and move from left to right. While doing so, we maintain an array sum which maintains the vertical sum of the selected row range. This sum array and vertical sum matrix will help us find the sum for a new sub matrix in O(1) time. So the total time complexity will be O(n^3). O(n^2) for row range, and we will have a O(column) operation inside that. So the total complexity will become O(n^3).