Modified Algorithm for 2D Maximum Sum Subarray Problem

This paper presents a two-phase adaptive algorithm to solve the 2-Dimensional Maximum Sum Sub-array Problem. By reframing the search order to establish a single-column baseline first, the algorithm generates mathematical pruning bounds in O(NM) time. These bounds are utilized in a second phase to skip unpromising multi-column scans in O(1) time. This “Two-Phase” approach achieves a quadratic best-case floor of O(M2 + NM), while significantly improving the expected performance across typical data distributions and maintaining the cubic worst-case. This adaptive strategy effectively bridges the gap between theoretical sub-cubic complexity and practical implementation.