4

Suppose you have an N × N matrix where each row has exactly one nonzero element and each column has exactly one nonzero element (the nonzero elements can be either positive or negative). We want to find the maximum-sum submatrix. How efficiently can we do so?

The matrix has dimension N × N and only N non-zero elements. N is so big, so I can't use an O(N3) algorithm. Does anyone know how to solve this in time O(N2), O(N log N), or some other time complexity like this?

Thanks!

Khurshid
  • 2,654
  • 2
  • 21
  • 29
  • What is the "trivial situation"? – Matt Feb 07 '14 at 20:22
  • I'm assuming that the location of the N non-zero elements is unknown (not a sparse matrix) and the values are both positive and negative? – IdeaHat Feb 07 '14 at 20:31
  • If you're not using a sparse matrix then O(N^2) is the best you can possibly do, since you at least have to read every element. There's probably some generalization of Kadane's Algorithm into two dimensions. http://stackoverflow.com/questions/12339280/find-max-sum-of-elements-in-array – Adam Feb 07 '14 at 20:35
  • 1
    O(N^3) with Kadane's in 2D. http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/ – IdeaHat Feb 07 '14 at 20:40
  • 1
    If each column has exactly one nonzero element, then you can collapse the matrix into an array and apply Kadane's algorithm with O(N) complexity. But since you still probably have to go through all elements (in order to find those nonzeros) you obtain O(N^2) as @Adam noticed. – freakish Feb 07 '14 at 21:06
  • 2
    @freakish not so, because a submatrix does not necessarily collapse to a contiguous subvector of the collapsed array. – Brian Bi Feb 07 '14 at 21:10
  • @BrianBi Of course it does. You can just consider submatrices composed of whole columns. – freakish Feb 07 '14 at 21:11
  • @freakish take the submatrix consisting of the first two rows: XOO OOX OXO – Brian Bi Feb 07 '14 at 21:13
  • @BrianBi Ah, I see. Right, right. – freakish Feb 07 '14 at 21:18
  • @freakish how does this solve the problem? If you reorder the columns then submatrices are not mapped to submatrices. – Brian Bi Feb 07 '14 at 21:25
  • @BrianBi Yep, you're right. I guess there are no shortcuts. – freakish Feb 07 '14 at 21:27
  • How is the matrix stored? – Dave Feb 08 '14 at 00:17

1 Answers1

2

If you want to find the maximum sum subrectangle, you can do it in O(n^2 log n) time using the algorithm described here maximum sum subrectangle in a sparse matrix . This beats Kadane's algorithm which is O(n^3).

Community
  • 1
  • 1
user2566092
  • 4,631
  • 15
  • 20