arrays - 矩阵数组部分的最大和

Question

我被困在一个简单的问题上，我正在寻找比我的更好的解决方案。

我有一个整数矩阵数组 (tab[N][M]) 和整数 (k)，我必须找到最小的矩形(子矩阵数组)它的元素之和大于 k

所以，我目前的解决方案尝试是:

1. 创建额外的矩阵数组 (sum[N][M]) 和整数 solution = infinity

2. 对于每个 1 <i <= N + 1 和 1 <j <= M + 1

   sum[ i ][ j ] = sum[ i - 1 ][ j ] + sum [ i ][ j - 1] + tab[ i  ] [ j ] - sum[ i - 1] [ j - 1]  
   

3. 然后查看从 (x, y) 开始到 (a, b) 结束的每个矩形 f.e

   Rectangle_(x,y)_(a,b) = sum[ a ][ b ] - sum[ a - x ] [ b ] - sum[ a ][ b - y ] + sum[ a - x ][ b - y ]
   

   如果 Rectangle_(x,y)_(a,b) >= k 则 solution = current_solution 和 (a - x) * (b - y) 的最小值

但是这个解决方案很慢(四次时间)，有没有可能让它更快？我正在寻找迭代对数时间(或更差/更好)。我设法减少了我的时间，但并没有显着减少。

Answer 1

如果矩阵仅包含 >= 0 的值，则在 1D 情况下存在线性时间解，可以扩展为 2D 情况下的立方时间解。

对于一维情况，您从左到右进行一次传递，在数组上滑动一个窗口，边移动边拉伸(stretch)或收缩它，以便区间中包含的数字总和至少为 k(或突破如果这是不可能的循环)。

最初，将区间的左索引绑定(bind)为第一个元素，右索引绑定(bind)为-1，然后循环:

• 将右边界递增 1，然后继续递增，直到区间内的值总和 > k，或到达数组末尾。
• 在不让值之和小于或等于 k ​​的情况下，增加左边界以尽可能缩小间隔。
• 如果结果是一个有效区间(意味着第一步没有找到有效区间就没有到达数组的末尾)然后将它与目前为止的最小值进行比较，并在必要时进行更新。

如果允许负值，这将不起作用，因为在第二步中，您需要能够假设缩小间隔总是会导致更小的总和，因此当总和低于 k 时，您知道这是可能的最小值对于给定的间隔端点。

对于 2D 情况，您可以遍历所有可能的子矩阵高度，并遍历给定高度的每个可能的起始行，并对每一行执行此水平扫描。

在伪代码中:

假设您有一个函数 rectangle_sum(x, y, a, b)，它返回从 (x, y) 到 (a, b) 的值之和，并在 O( 1) 一次使用求和面积表。

for(height = 1; height <= M; height++)  // iterate over submatrix heights
{
    for(row = 0; row <= (M-h); row++)   // iterate over all rows
    {
        start = 0; end = -1; // initialize interval
        while(end < N)  // iterate across the row
        {
            valid_interval = false;
            // increment end until the interval sums to > k:
            while(end < (N-1))
            {
                end = end + 1;
                if(rectangle_sum(start, row, end, row + height) > k)
                {
                    valid_interval = true;
                    break;
                }
            }
            if(!valid_interval)
                break;
            // shrink interval by incrementing start:
            while((start < end) && 
                rectangle_sum(start+1, row, end, row + height) > k))
                start = start + 1;

            compare (start, row), (end, row + height) with current smallest
            submatrix and make it the new current if it is smaller
        }
    }
}