Question

Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum.

Solution

I wrote about this question before: [Question] Max Sum In A 2D Array (sub-matrix), and the solution gave a better time complexity (O(n³)) than in the book (O(n⁴)).

1. locate a row - O(n)
2. locate another row - O(n)
3. compute sub value of that column - O(n), and then find largest subarray in array - also O(n)
4. The above 3 steps each take O(n) time, total time is O(n³).

Please refer to the other post for more detail.