最大总和子矩形的稀疏矩阵 [英] maximum sum subrectangle in a sparse matrix

问题描述

查找最大总和子矩形中的 N×N个矩阵可以在使用来完成为O（n ^ 3）时间2-D kadane的算法，如在其他职位指出。但是，如果矩阵是稀疏的，特别是 O（N）的非零项，可以在为O（n ^ 3）时被殴打？

Finding the maximum sum subrectangle in an NxN matrix can be done in O(n^3) time using 2-d kadane's algorithm, as pointed out in other posts. However, if the matrix is sparse, specifically O(n) non-zero entries, can the O(n^3) time be beaten?

如果有帮助，对当前应用程序我感兴趣的，就足够了有一个解决方案，假定在每一行和在矩阵的每列的至多一个非零值。然而，在我未来的应用这种假设可能不适合（只是稀疏将举行），反正我的数学直觉是，有可能是很好的解决方案（S），简单地利用稀疏，不进一步利用的事实，矩阵一个对角和一个置换矩阵的乘积。

If it helps, for the current application I'm interested in, it would suffice to have a solution that assumes at most one non-zero value in each row and in each column of the matrix. However, in my future applications this assumption might not be appropriate (just sparsity will hold), and anyway my mathematical intuition is that there may be good solution(s) that simply exploit sparsity and don't further exploit the fact that the matrix is a product of a diagonal and a permutation matrix.

推荐答案

是的，这是可以做到更好。

Yes, it can be done better.

首先，让我们想想的数据结构，使我们能够

First of all, let's think about a data structure which allows us to

1. 在更新底层一维数组中的任何单个值O（LOGN）时间
2. 找到数组的最大子阵的总和 O（1）时间

1. Update any single value of the underlying 1D array in O(logn) time
2. Find the sum of maximum subarray of the array in O(1) time

其实，平衡二叉树，看起来像下面可以做的工作。树结构可以被描述为：

Actually, a balanced binary tree which looks like below can do the job. The tree structure can be described as:

1. 树重新presents的阵列的每个元素的每个叶节点。
2. 如果一个内部节点覆盖范围 [A，B] ，它的左子覆盖范围 [A，C] 其右子覆盖范围 [C + 1，B] ，其中 C =楼（（A + B）/ 2））。

3. 根节点覆盖范围 [1，N] 。

1. Every leaf node of the tree represents every element of the array.
2. If an internal node covers range [a, b], its left child covers range [a, c] and its right child covers range [c + 1, b], where c = floor((a + b) / 2)).

3. The root node covers range [1, n].

                      O
                    /   \
                  /       \
                /           \
              /               \
            /                   \
          O                       O
        /   \                   /   \
       /     \                 /     \
      /       \               /       \
    O           O           O           O
   / \         / \         / \         / \
 o     o     o     o     o     o     o     o
A[1]  A[2]  A[3]  A[4]  A[5]  A[6]  A[7]  A[8]

有连接到每一个节点 v （包括叶节点和内部节点）4个领域：

There are 4 fields attached to every node v (including leaf nodes and internal nodes):

• S [V] ：所有的值的的总和v 的范围
• M [V] ：最大子阵列金额在 v 的范围
• L [V] ：最大子数组，在对左侧开始v 的范围之
• 研究[V] ：最大子数组，在右侧的结束v 之和的范围

• S[v]: the sum of all values in v's range
• M[v]: the maximum subarray sum in v's range
• L[v]: the sum of maximum subarray that starts at the left side of v's range
• R[v]: the sum of maximum subarray that ends at the right side of v's range

根据上述定义，我们可以发现以下更新规则：

Based on the above definitions, we may find the following updating rules:

• 对于任何一个叶子结点 v ， S [V] = A [V] ， M [V] = L [V] = R [V] =最大值{0，A [V]}
• 对于任何一个内部节点 v 及其子→和研究，
  
  • S [V] = S [L] + S [R]
  • M [V] =最大值{M [L]，M [R]，R [L] + L [R]}
  • L [V] =最大值{L [L]，L [R] + S [L]}
  • 研究[V] =最大值{红[R]，R [L] + S [R]}
  • For any leaf node v, S[v] = A[v], M[v] = L[v] = R[v] = max{0, A[v]}
  • For any internal node v and its children l and r,
    
    • S[v] = S[l] + S[r]
    • M[v] = max{M[l], M[r], R[l] + L[r]}
    • L[v] = max{L[l], L[r] + S[l]}
    • R[v] = max{R[r], R[l] + S[r]}

    最后，我们可以实现在开头提到的操作。

    Finally, we can implement the operations mentioned in the beginning.

    • 要更新 A [1] ，我们可能会在树中寻找相应的叶节点，并更新沿其路径根使用上述规则的领域。
    • 的最大子阵列和是简单地 M [根] 。
    • To update A[i], we may find the corresponding leaf node in the tree, and update the fields along its path to the root using the above rules.
    • The maximum subarray sum is simply M[root].

    现在让我们来讨论如何找到利用这种数据结构的最大矩形。如果我们解决了上行和矩形的下排为我和第Ĵ日行，问题变成是一维的最大子阵列和问题，其中 A [K] =总和{B [i..j，K]} 。关键的观点是，对于固定我，如果我们列举Ĵ升序排列，我们可以用上面的数据结构保持基本的一维数组，并找到了答案非常快。伪code介绍了想法：

    Now let's discuss how to find the maximum rectangle using this data structure. If we fix the upper row and the lower row of the rectangle to ith and jth rows, the problem turns to be the 1D maximum subarray sum problem, where A[k] = sum{B[i..j, k]}. The key insight is that, for a fixed i, if we enumerate j in ascending order, we can use the above data structure to maintain the underlying 1D array and find the answer very quickly. The pseudocode describes the idea:

    result = 0
    for i in (1, 2, ..., n)
        set all fields of the binary tree T to 0
        for j in (i, i + 1, ..., n)
            for any k where B[j, k] != 0
                T.update(k, A[k] + B[j, k])
            result = max{M[root], result}
    return result
    

    假设矩阵包含 M 非零元素，该算法的时间复杂度为 O（MN：LOGN）。在你的情况 M = O（N），所以时间复杂度为为O（n ^ 2 LOGN）并比为O（n ^ 3）。

    Suppose the matrix contains m non-zero elements, the time complexity of this algorithm is O(mn logn). In your case m = O(n), so the time complexity is O(n^2 logn) and is better than O(n^3).

    这篇关于最大总和子矩形的稀疏矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！