求矩阵任意子矩阵中的最大元素

我给出一个矩阵N x M。对于长度的子矩阵X从位置开始(a, b)我必须找到子矩阵中存在的最大元素。

我的方法：

1. 按照问题说的做： 简单2个循环

   for(i in range(a, a + x))
   for(j in range(b, b + x)) max = max(max,A[i][j]) // N * M

提前一点：

 1. Make a segment tree for every i in range(0, N)
 2. for i in range(a, a + x) query(b, b + x)    // N * logM

有没有更好的解决方案，复杂度仅为 O(log n) ？

稀疏表算法方法 :-<O( N x M x log(N) x log(M)) , O(1)>.

预计算时间 - O( N x M x log(N) x log(M))
查询时间 - O(1)

为了理解此方法，您应该了解使用一维稀疏表算法查找 RMQ。

我们可以使用 2D 稀疏表算法来查找范围最小查询。

我们在一维领域所做的事情：-
我们预处理RMQ对于长度的子数组2^k使用动态规划。我们将保留一个数组M[0, N-1][0, logN] where M[i][j]是子数组中最小值的索引，从i。 用于计算M[i][j]我们必须在区间的前半部分和后半部分中寻找最小值。很明显，小碎片有2^(j – 1)长度，所以计算的伪代码是：-

if (A[M[i][j-1]] < A[M[i + 2^(j-1) -1][j-1]])
    M[i][j] = M[i][j-1]
else 
    M[i][j] = M[i + 2^(j-1) -1][j-1]

Here A是存储值的实际数组。一旦我们预处理了这些值，让我们展示如何使用它们来计算RMQ(i,j)。这个想法是选择两个完全覆盖区间的块[i..j]并找出它们之间的最小值。让k = [log(j - i + 1)]。用于计算RMQ(i,j)我们可以使用以下公式：-

if (A[M[i][k]] <= A[M[j - 2^k + 1][k]])
    RMQ(i, j) = A[M[i][k]]
else 
    RMQ(i , j) = A[M[j - 2^k + 1][k]]

对于二维：-
类似地，我们也可以将上述规则扩展到二维，这里我们进行预处理RMQ对于长度的子矩阵2^K, 2^L使用动态编程并保留一个数组M[0,N-1][0, M-1][0, logN][0, logM]. Where M[x][y][k][l]是子矩阵中最小值的索引，从[x , y]并且有长度2^K, 2^L分别。 计算伪代码M[x][y][k][l] is:-

M[x][y][i][j] = GetMinimum(M[x][y][i-1][j-1], M[x + (2^(i-1))][y][i-1][j-1], M[x][y+(2^(j-1))][i-1][j-1], M[x + (2^(i-1))][y+(2^(j-1))][i-1][j-1])

Here GetMinimum函数将返回提供的元素中最小元素的索引。现在我们已经预处理好了，让我们看看如何计算RMQ(x, y, x1, y1). Here [x, y]子矩阵的起点和[x1, y1]表示子矩阵的端点表示子矩阵的右下点。这里我们必须选择四个完全覆盖的子矩阵块[x, y, x1, y1]并找到其中的最小值。让k = [log(x1 - x + 1)] & l = [log(y1 - y + 1)]。用于计算RMQ(x, y, x1, y1)我们可以使用以下公式：-

RMQ(x, y, x1, y1) = GetMinimum(M[x][y][k][l], M[x1 - (2^k) + 1][y][k][l], M[x][y1 - (2^l) + 1][k][l], M[x1 - (2^k) + 1][y1 - (2^l) + 1][k][l]);

上述逻辑的伪代码：-

// remember Array 'M' store index of actual matrix 'P' so for comparing values in GetMinimum function compare the values of array 'P' not of array 'M' 
SparseMatrix(n , m){ // n , m is dimension of matrix.
    for i = 0 to 2^i <= n:
        for j = 0 to 2^j <= m:
            for x = 0 to x + 2^i -1 < n :
                for y = 0 to y + (2^j) -1 < m:
                    if i == 0 and j == 0:
                        M[x][y][i][j] = Pair(x , y) // store x, y
                    else if i == 0:
                        M[x][y][i][j] = GetMinimum(M[x][y][i][j-1], M[x][y+(2^(j-1))][i][j-1])
                    else if j == 0:
                        M[x][y][i][j] = GetMinimum(M[x][y][i-1][j], M[x+ (2^(i-1))][y][i-1][j])
                    else 
                        M[x][y][i][j] = GetMinimum(M[x][y][i-1][j-1], M[x + (2^(i-1))][y][i-1][j-1], M[x][y+(2^(j-1))][i-1][j-1], M[x + (2^(i-1))][y+(2^(j-1))][i-1][j-1]);
}
RMQ(x, y, x1, y1){
    k = log(x1 - x + 1)
    l = log(y1 - y + 1)
    ans = GetMinimum(M[x][y][k][l], M[x1 - (2^k) + 1][y][k][l], M[x][y1 - (2^l) + 1][k][l], M[x1 - (2^k) + 1][y1 - (2^l) + 1][k][l]);
    return P[ans->x][ans->y] // ans->x represent Row number stored in ans and similarly ans->y represent column stored in ans
}