Max sum of sub-matrix no larger than K

  • 0

    Given a 2D matrix A and an integer K, find the max sum of A's sub-matrix. The max sum should be no larger than K.


    Given A = [
      [-1, 0, 1],
      [0, -2, 3]
    K = 2

    The answer is 2. Because the sum of sub-matrix[[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than K(K = 2).

  • 0

    @1337c0d3r OK, I've reedited my post.

  • 0

    The brute force solution is O(n^4). By finding all sub-matrix and filter it. So we know the solution should be better than O(n^4). Then there are the recursive algorithm. If we merge a column or a row in every step, then we have a smaller matrix. But then you will have to pick O(n^2) starting points and given a starting point, the recursive merge phase could take O(n^3). So that is no better. If recursion is not better, then it's obvious we should use dynamic programming. Here is something that kind of works. Let d(i, j, k) be the sub-matrix sum that is no larger than k and starting from (i,j). For this to work, we'll need to assume K and the values in the matrix are bounded by some constant.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.