Maximum sum rectangle in a 2D matrix

Problem: Given a 2D array, find the maximum sum submatrix in it.

Example:

Input: Above image
Output: 18 
Explanation: Maximum sum sub matrix is highlighted by red color and the sum of this rectangle 18.

Approach: We can apply the brute force approach here and get the sum of all the possible rectangles and then we can return the maximum of all these sums but it will take O(n ^ 6) time. Let's see how we can solve it efficiently.

We can use Kadane's algorithm which is used to find the maximum sum subarray in a 1D array in linear time. Here is the algorithm:

• maxSum = int.Min
• FOR left = 0 to number of columns - 1
•  Declare a 1D array say tempSumArray of length = number of rows. Initialize it with all 0s.
• FOR right = left to number of columns - 1
• For i = 0 to number of rows - 1
• tempSumArray[i] = tempSumArray[i] + matrix[i][right]
• currSum = KadanesAlgo(tempSumArray)
• maxSum = MAX(currSum, maxSum)
• Return maxSum

That's it! Please note that it's complexity will be O(m * n ^ 2) where m and n are number of rows and columns respectively. That means if the number of columns are much larger than the number of rows then we have a problem so in that case we can use rows in place of columns and columns in place of rows in the above code to make it O(m^2 * n) or we can rotate the array 90 degree clockwise.

Implementation in C#:

        public int MaxSumSubmatrix(int[][] matrix)

        {

            if (matrix?.Length == 0)

            {

                return 0;

            }

            int maxSum = int.MinValue;

            for (int left = 0; left < matrix[0].Length; ++left)

            {

                int[] sumArray = new int[matrix.Length];

                for (int right = left; right < matrix[0].Length; ++right)

                {

                    for (int i = 0; i < matrix.Length; ++i)

                    {

                        sumArray[i] += matrix[i][right];

                    }

                    int currSum = MaxSumSubArray(sumArray);

                    maxSum = Math.Max(maxSum, currSum);

                }

            }

            return maxSum;

        }

        public int MaxSumSubArray(int[] nums)

        {

            if (nums?.Length == 0)

            {

                return 0;

            }

            int sum = int.MinValue, currSum = 0, maxNum = nums[0];

            for (int i = 0; i < nums.Length; ++i)

            {

                // if all elem of array are negative the maxNo is the max sum

                maxNum = Math.Max(maxNum, nums[i]);

                currSum += nums[i];

                if (currSum < 0)

                {

                    currSum = 0;

                }

                else

                {

                    sum = Math.Max(currSum, sum);

                }

            }

            return sum;

        }

Complexity: O(m * n^2) => O(n^3)