Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum.
I wrote about this question before: [Question] Max Sum In A 2D Array (sub-matrix), and the solution gave a better time complexity (O(n3)) than in the book (O(n4)).
- locate a row - O(n)
- locate another row - O(n)
- compute sub value of that column - O(n), and then find largest subarray in array - also O(n)
- The above 3 steps each take O(n) time, total time is O(n3).
Please refer to the other post for more detail.