Given a 2D array, find the maximum sum subarray in it. For example, in the following 2D array, the maximum sum subarray is highlighted with blue rectangle and sum of this subarray is 29 1 2 -1-4-20 This problem is mainly an extension of Largest Sum Contiguous Subarray for 1D array The naive solution for this problem is to check every possible rectangle in given 2D array.This solution re- quires 4 nested loops and time complexity of this solution would be O(n 4)