在 C++ 中查找其边界上整数和最大的矩形

Question

我目前正在学习和练习本文档中的试错方法，我偶然发现了这个问题：

\n

\n

给定一个包含m行和n的整数网格。找出边与格子边缘平行（每条边的长度都大于1）且位于其边界上的数字之和最大的矩形。

\n

\n
• 输入：
  \n第一行包含 2 个整数m和n。
  \n下一个m行：每行包含 n 个描述网格行的整数。
\n
• 输出：
  \n我们找到的最大总和。
\n
• 约束：
  \n2 <= m，n <= 500
  \n运行时 < 3\xe2\x80\xafs
\n

\n

例如：

\n

输入：

\n

5 4\n\xe2\x80\x87 9\xe2\x80\x87-2\xe2\x80\x87-1\xe2\x80\x87 3\n-10\xe2\x80\x87-5\xe2\x80\x87 1\xe2\x80\x87-4\n\xe2\x80\x87 1\xe2\x80\x87-1\xe2\x80\x87 2\xe2\x80\x87-2\n\xe2\x80\x87 3 \xe2\x80\x870\xe2\x80\x87 0\xe2\x80\x87-1\n\xe2\x80\x87 2\xe2\x80\x87 2\xe2\x80\x87-1\xe2\x80\x87 2\n

\n

输出：

\n

8\n

\n

解释：

\n

这里，位于其边界上的数字之和最大的矩形是：

\n

1\xe2\x80\x87-1\xe2\x80\x87 2
\n3\xe2\x80\x87 0\xe2\x80\x87 0
\n2\xe2\x80\x87 2\xe2\x80\x87-1

\n

总和为 1 + -1 + 2 + 0 + -1 + 2 + 2 + 3 = 8

\n

\n

尝试利用最大总和矩形的第三方艰难输入：

\n

5 5\n0  1\xe2\x80\x87 0\xe2\x80\x87 1  0\n0  0\xe2\x80\x87-1\xe2\x80\x87 0  0\n0  0\xe2\x80\x87 0\xe2\x80\x87 0  0\n0  0\xe2\x80\x87-4\xe2\x80\x87 0  0\n0  1\xe2\x80\x87 0\xe2\x80\x87 2  0\n

\n

我尝试创建数组p[m][n]的前缀和，并且可以计算右下位置为 ( i, j) 且矩形的宽度和高度为 ( w, h) 的矩形的边框和：

\n

sum = (p[i][j]     - p[i][j-w]   - p[i-h][j]   + p[i-h][j-w])\n    - (p[i-1][j-1] - p[i][j-w+1] - p[i-h+1][j] + p[i-h+1][j-w+1])\n

\n

这里，(p[i][j] - p[i][j-w] - p[i-h][j] + p[i-h][j-w])计算矩形所有整数的和，并(p[i-1][j-1]—p[i][j-w+1] - p[i-h+1][j] + p[i-h+1][j-w+1])计算矩形的内部和（不包括边框）。

\n

我必须使用四个嵌套的for循环来查找i、j、w和的所有可能值h，并相应地更新最大总和，这使我超出了时间限制 ( TLE )，因为约束的运行时间少于 1 秒。

\n

---

\n

正如用户建议的那样，我创建了辅助函数来帮助我计算矩形的边框总和，其中左上角位置为 ( , x0) y0，右下位置为 ( x1,y1 ) 的矩形的边框总和，这帮助我修复了一些情况：

\n

int sum(int x0, int y0, int x1, int y1)\n{\n    if (x0 < x1 && y0 < y1)\n    {\n        return p[x1][y1] - p[x0][y1] - p[x1][y0] + p[x0][y0];\n    }\n    else if (x0 == x1 && y0 == y1)\n    {\n        return a[x0][y0];\n    }\n    else\n    {\n        return 0;\n    }\n}\n\nint border(int x0, int y0, int x1, int y1)\n{\n    return sum(x0, y0, x1, y1) - sum(x0+1, y0+1, x1-1, y1-1);\n}\n

\n

但我仍然必须找到所有可能的值x0, y0, x1, y1，这给了我一个 TLE。

\n

---

\n

结果发现时间限制是3秒。

\n

Answer 1

好的，我将其作为可能的动态编程解决方案提交。我相信它是 O(N ³ ) （或者，如果 m 和 n 非常不同，则严格为 mn(m+n) ）。对于 500x500 的随机矩阵，需要一秒钟左右（根据我的手表）。对于 100x100 随机矩阵，它给出与暴力破解相同的结果。

这个想法是构造一个临时的 - 形式上是 B[i][j][w]，但如果仔细完成，那么只需要存储 B[j][w] 两个连续的行 - 这代表了一个的最佳总和宽度为 w 的矩形，结束于（右下）[i][j]。这需要对 i,j,w 进行循环 - 因此 O(N ³ )。

从之前的最佳结果逐行构建它，我相信每次只有两个候选者（如果这个图没有多大意义，我深表歉意）

   //                 *-----*                 
   //                 |     |                         
   // Either          |     |                 or
   //                 |     |                         
   //                 o     o                              o-----o
   //                 *-----*                              *-----*

下面的代码针对（可选）Motomotes 的示例 1 和 2 以及大型随机矩阵进行了测试。为了进行测试，还有一个强力求解器（但不必费心在大型矩阵上使用它）。请注意，如果矩阵的宽度大于深度，那么我首先对其进行转置（为了方便起见）。

相关例程是int bestRectangleSum( vector<vector> &M )

#include <iostream>
#include <iomanip>
#include <vector>

#include <cstdlib>
#include <ctime>

using namespace std;

//------------------------------------------------------------------------------

template<typename T>
ostream &operator << ( ostream &out, const vector<vector<T>> &M )
{
   for ( auto &row : M )
   {
      for ( auto e : row ) out << setw( 10 ) << e << "  ";
      out << '\n';
   }
   return out;
}

//------------------------------------------------------------------------------

template<typename T>
vector<vector<T>> transpose( const vector<vector<T>> &M )
{
   int m = M.size(), n = M[0].size();
   vector<vector<int>> result( n, vector<int>( m ) );

   for ( int i = 0; i < m; i++ )
   {
      for ( int j = 0; j < n; j++ ) result[j][i] = M[i][j];
   }

   return result;
}

//------------------------------------------------------------------------------

vector<vector<int>> fillRand( int m, int n, int lower, int higher )
{
   vector<vector<int>> M( m, vector<int>( n ) );

   for ( int i = 0; i < m; i++ )
   {
      for ( int j = 0; j < n; j++ ) M[i][j] = lower + rand() % ( higher - lower + 1 );
   }

   return M;
}

//------------------------------------------------------------------------------

int bestRectangleSum( vector<vector<int>> &M )
{
   int m = M.size(), n = M[0].size();

   // Transpose if necessary to work with smaller maximum width
   if ( m < n )
   {
      M = transpose( M );
      int t = m;   m = n;  n = t;
   }

   // sumLeft[i][j] holds the cumulative sum to the left of (and including) [i][j])
   vector<vector<int>> sumLeft( m, vector<int>( n, 0 ) );
   for ( int i = 0; i < m; i++ )
   {
      sumLeft[i][0] = M[i][0];
      for ( int j = 1; j < n; j++ ) sumLeft[i][j] = sumLeft[i][j-1] + M[i][j];
   }

   // Row by row, B[j][w] will hold the best rectangle sum for a rectangle of width w finishing (bottom-right) at (i,j)
   int best = M[0][0] + M[0][1] + M[1][0] + M[1][1];
   vector<vector<int>> B( n, vector<int>( n + 1, 0 ) );

   // First non-zero B will be for second row (i=1)      This part: O(N^2)
   for ( int j = 1; j < n; j++ )
   {
      for ( int w = 2; w <= j; w++ ) 
      {
         B[j][w] = sumLeft[0][j] - sumLeft[0][j-w] + sumLeft[1][j] - sumLeft[1][j-w];
         if ( B[j][w] > best ) best = B[j][w];
      }
      B[j][j+1] = sumLeft[0][j] + sumLeft[1][j];
      if ( B[j][j+1] > best ) best = B[j][j+1];
   }

   // Subsequent rows - each w will give rise to two candidates:          This part O(N^3)
   //                 *-----*                 
   //                 |     |                         
   // Either          |     |                 or
   //                 |     |                         
   //                 o     o                              o-----o
   //                 *-----*                              *-----*
   //
   for ( int i = 2; i < m; i++ )
   {
      auto previous = B;
      for ( int j = 1; j < n; j++ )
      {
         for ( int w = 2; w <= j + 1; w++ )
         {
            int oldBase = sumLeft[i-1][j];
            int newBase = sumLeft[i  ][j];
            if ( w <= j ) 
            {
               oldBase -= sumLeft[i-1][j-w];
               newBase -= sumLeft[i  ][j-w];
            }
            int oldBaseMinusEnds = oldBase - M[i-1][j] - M[i-1][j-w+1];
            int candidate1 = previous[j][w] + newBase - oldBaseMinusEnds;
            int candidate2 = oldBase + newBase;
            B[j][w] = max( candidate1, candidate2 );
            if ( B[j][w] > best ) best = B[j][w];
         }
      }
   }
   return best;
}

//------------------------------------------------------------------------------

int bruteForce( const vector<vector<int>> &M )
{
   int m = M.size(), n = M[0].size();
   vector<vector<int>> sumLeft( m, vector<int>( n, 0 ) ), sumAbove( m, vector<int>( n, 0 ) );
   for ( int i = 0; i < m; i++ )
   {
      sumLeft[i][0] = M[i][0];
      for ( int j = 1; j < n; j++ ) sumLeft[i][j] = sumLeft[i][j-1] + M[i][j];
   }
   for ( int j = 0; j < n; j++ )
   {
      sumAbove[0][j] = M[0][j];
      for ( int i = 1; i < m; i++ ) sumAbove[i][j] = sumAbove[i-1][j] + M[i][j];
   }

   int best = M[0][0] + M[0][1] + M[1][0] + M[1][1];
   for ( int i1 = 0; i1 < m - 1; i1++ )
   {
      for ( int i2 = i1 + 1; i2 < m; i2++ )
      {
         for ( int j1 = 0; j1 < n - 1; j1++ )
         {
            for ( int j2 = j1 + 1; j2 < n; j2++ )
            {
               int candidate = sumLeft[i1][j2] + sumLeft[i2][j2];
               if ( j1 > 0 ) candidate -= ( sumLeft[i1][j1-1] + sumLeft[i2][j1-1] );
               if ( i2 - 1 > i1 ) candidate += ( sumAbove[i2-1][j1] - sumAbove[i1][j1] + sumAbove[i2-1][j2] - sumAbove[i1][j2] );
               if ( candidate > best ) best = candidate;
            }
         }
      }
   }
   return best;
}

//------------------------------------------------------------------------------

int main()
{
// Example 1 (first example of Motomotes)
   vector<vector<int>> M1 = { {  2, -8, -9, -2,  8 },
                              {  6,  0,  2,  7,  4 },
                              { -6, -8, -4, -4,  1 },
                              {  0, -8, -1,  4,  4 } };

// Example 2 (second example of Motomotes)
   vector<vector<int>> M2 = { {   9,  -2,  -1,   3 },
                              { -10,  -5,   1,  -4 },
                              {   1,  -1,  12,  -2 },
                              {   3,   8,   0,  -1 },
                              {   2,   2,  -1,   2 } };

// Example 3 (large random matrix)
   const int m = 100, n = 100, lower = -100, higher = 100;
   srand( time( 0 ) );
   auto M3 = fillRand( m, n, lower, higher );

   auto M = M1;

   cout << M << '\n';                                               // <==== comment out for large matrices
   cout << "Main solver: " << bestRectangleSum( M ) << '\n';        // <==== main solution
   cout << "Brute force: " << bruteForce( M ) << '\n';              // <==== don't use for large matrices
}

//------------------------------------------------------------------------------

Monomotes 示例 1 的输出：

         2          -8          -9          -2           8  
         6           0           2           7           4  
        -6          -8          -4          -4           1  
         0          -8          -1           4           4  

Main solver: 22
Brute force: 22

Answer 2

这是一个O(m*m*n)及时的O(m*n)内存算法。（如果n<m使用转置网格来代替，则保证m<=n。）

首先，计算两个给出行和列前缀和的数组：

// prefix_row : (i,j) -> sum of values from (i,0) to (i,j) inclusive
// prefix_col : (i,j) -> sum of values from (0,j) to (i,j) inclusive

O(1)使用这些，可以在给定对角(i0,j0)和的情况下及时计算周长和(i1,j1)：

perimeter_sum(i0,j0,i1,j1) =
    prefix_col[i1][j0] - prefix_col[i0][j0] // left
  + prefix_col[i1][j1] - prefix_col[i0][j1] // right
  + prefix_row[i0][j1] - prefix_row[i0][j0] // top
  + prefix_row[i1][j1] - prefix_row[i1][j0] // bottom
  + grid[i0][j0] - grid[i1][j1] // compensate missing and double-counted

接下来，将它们分为两个总和：依赖于 的总和j0和依赖于 的总和j1。让我们分别命名它们x和y：

perimeter_sum(i0,j0,i1,j1) = x(i0,i1,j0) + y(i0,i1,j1)

在哪里

x(i0,i1,j0) = prefix_col[i1][j0] - prefix_col[i0][j0] -
              prefix_row[i1][j0] - prefix_row[i0][j0] + grid[i0][j0]

y(i0,i1,j1) = prefix_col[i1][j1] - prefix_col[i0][j1] +
              prefix_row[i1][j1] + prefix_row[i0][j1] - grid[i1][j1]

现在的策略是循环i0和i1。i0<i1对于给定的i0和i1，现在可以及时计算max(x+y)过度变化，因为和是和的独立函数。总体而言，这会及时找到 的最终最大值。j0<j1O(n)xyO(1)j0j1O(m*m*n)x+y

下面是有效的 C++ 代码。

#include <iostream>
#include <limits>
#include <vector>

// Prepare 2 arrays:
// prefix_row : (i,j) -> sum of values from (i,0) to (i,j) inclusive
// prefix_col : (i,j) -> sum of values from (0,j) to (i,j) inclusive

int m, n;
std::vector<std::vector<int> > grid;
std::vector<std::vector<int> > prefix_row;
std::vector<std::vector<int> > prefix_col;

void set_grid() {
  std::cin >> m >> n;
  if (m <= n) {
    grid.resize(m, std::vector<int>(n));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        std::cin >> grid[i][j];
      }
    }
  } else {
    std::swap(m, n); // import transposed grid so that m < n.
    grid.resize(m, std::vector<int>(n));
    for (int j = 0; j < n; ++j) {
      for (int i = 0; i < m; ++i) {
        std::cin >> grid[i][j];
      }
    }
  }
}

void set_prefix_row() {
  prefix_row.resize(m, std::vector<int>(n));
  for (int i = 0; i < m; ++i) {
    int prefix_sum = 0;
    for (int j = 0; j < n; ++j) {
      prefix_sum += grid[i][j];
      prefix_row[i][j] = prefix_sum;
    }
  }
}

void set_prefix_col() {
  prefix_col.resize(m, std::vector<int>(n));
  for (int j = 0; j < n; ++j) {
    int prefix_sum = 0;
    for (int i = 0; i < m; ++i) {
      prefix_sum += grid[i][j];
      prefix_col[i][j] = prefix_sum;
    }
  }
}

int x(int const i0, int const i1, int const j0) {
  return prefix_col[i1][j0] - prefix_col[i0][j0] -
         prefix_row[i1][j0] - prefix_row[i0][j0] + grid[i0][j0];
}

int y(int const i0, int const i1, int const j1) {
  return prefix_col[i1][j1] - prefix_col[i0][j1] +
         prefix_row[i1][j1] + prefix_row[i0][j1] - grid[i1][j1];
}

int get_max_sum() {
  int max_sum = std::numeric_limits<int>::min();
  for (int i0 = 0; i0 < m - 1; ++i0) {
    for (int i1 = i0 + 1; i1 < m; ++i1) {
      int max_x = std::numeric_limits<int>::min();
      for (int j = 1; j < n; ++j) {
        max_x = std::max(max_x, x(i0, i1, j - 1)); // O(1)
        max_sum = std::max(max_sum, max_x + y(i0, i1, j)); // O(1)
      }
    }
  }
  return max_sum;
}

int main() {
  set_grid();                        // O(m*n)
  set_prefix_row();                  // O(m*n)
  set_prefix_col();                  // O(m*n)
  int const max_sum = get_max_sum(); // O(m*m*n)
  std::cout << max_sum << std::endl;
  return 0;
}

信用：n. m.链接到该算法所基于的答案，并进行了一些修改/更正。

注意：如果您从此页面将示例网格数据复制并粘贴到输入文件中，则可能会由于非空白字符而无法工作。为了std::cin读入int值，它们必须用“常规”空白（如空格、制表符或换行符）分隔。