Woodstock Blog

a tech blog for general algorithmic interview questions

[CC150v4] 20.12 Sub-matrix With Largest Sum


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)).

  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(n3).

Please refer to the other post for more detail.