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

toe95027 于 2023-05-19 发布在其他

关注(0)|答案(2)|浏览(182)

bounty还有7天到期。回答此问题可获得+50声望奖励。greybeard想要引起更多关注这个问题：n.m.暗示了Kadane算法的一个应用，我不明白（从什么是数组y开始？）.不寻找一个详细说明的解决方案（（去）破坏完整的解决方案欢迎），但对于如何运行在显着更少的时间比O（（nm）²）提示-或证明下限Ω（（nm）²）.锁定10小时.此问题的评论已被禁用，但仍在接受新的答案和其他交互。Learn more。

我目前正在学习和实践this document的试错法，在那里我偶然发现了这个问题：
给定一个由 m 行和 n 列组成的整数网格。找出边与网格的边平行的矩形（每条边的长度大于1），并且位于其边界上的数字之和最大。

输入：

第一行包含两个整数 m 和 n。
下一个 m 行：每一行包含描述网格的一行的N个整数。

输出：

我们发现的最大金额。

制约因素：

2 <= m，n <= 500
运行时间< 3秒
例如：
输入：

5 4
  9 -2 -1  3
-10 -5  1 -4
  1 -1  2 -2
  3  0  0 -1
  2  2 -1  2

输出：

说明：
在这里，位于其边界上的数字之和最大的矩形是：
1-12
3 0 0
22比1
其和为1 + -1 +2 +0 + -1 +2 +2 +3 = 8
尝试利用最大和矩形的第三方坚韧输入：

5 5
0  1  0  1  0
0  0 -1  0  0
0  0  0  0  0
0  0 -4  0  0
0  1  0  2  0

我尝试创建数组的前缀和p[m][n]，可以计算右下角位置为（i，j），矩形的宽度和高度为（w，h）的矩形的边界和：

sum = (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])

这里，(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])计算矩形的内部和（不包括边界）。
我必须使用四个嵌套的 for 循环来找到i、j、w和h的所有可能值，并相应地更新最大和，这给了我一个超过时间限制（TLE）的限制，因为限制是 * 运行时间小于1秒 *。
正如一个用户所建议的，我创建了一些辅助函数来帮助我计算一个矩形的边框和，该矩形的左上角位置为（x0，y0），右下角位置为（x1，y1），这帮助我解决了一些问题：

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

int border(int x0, int y0, int x1, int y1)
{
    return sum(x0, y0, x1, y1) - sum(x0+1, y0+1, x1-1, y1-1);
}

但是，我仍然必须找到x0, y0, x1, y1的所有可能值，这给了我一个TLE。
时间限制是3秒。

c++

来源：https://stackoverflow.com/questions/76259392/find-rectangle-with-the-largest-sum-of-integers-that-lies-on-its-border-in-c

2条答案

按热度按时间

6tr1vspr1#

好的，我将此作为一个可能的动态编程解决方案提交。我相信它是O（N3）（或者，严格地说，如果m和n非常不同，则为mn（m+n））。对于一个500 X500的随机矩阵，它需要一秒钟左右（由我的手表）。对于100 x100随机矩阵，它给出了与蛮力相同的结果。
这个想法是构建一个临时的-形式上是B[i][j][w]，但如果仔细完成，则只需要存储两个连续行的B[j][w]-其中这表示宽度w结束（右下）在[i][j]的矩形的最佳和。这需要在i，j，w上循环，因此时间复杂度为O（N3）。
从之前的最佳结果中逐行构建，我相信每次只有两个候选项（如果此图没有太大意义，请道歉）

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

下面的代码测试了Motomotes的示例1和2（可选）以及一个大型随机矩阵。对于测试，还有一个蛮力求解器（但不要费心在大型矩阵上使用它）。注意，如果矩阵的宽度大于深度，那么我先转置它（为了方便）。
相关例程为int bestRectangleSum（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

赞(0）回复(0）举报 2023-05-19

c9x0cxw02#

正如一位用户所建议的，我尝试使用Kadane的算法来找到网格中的最大矩形和以及前缀和，以减去三角形的内部部分。这将时间复杂度降低到了O(n^3)，它在m = n = 500上运行良好

#include <bits/stdc++.h>

using namespace std;

int arr[500][500], pre[501][501];

// Kadane's algorithm
int kadane(int a[], int &start, int &end, int n)
{
    int s = 0, maxS = INT_MIN, tmpStart = 0;
    end = -1;

    for (int i = 0; i < n; i++)
    {
        s += a[i];
        if (s < 0)
        {
            s = 0;
            tmpStart = i + 1;
        }
        else if (s > maxS)
        {
            maxS = s;
            start = tmpStart;
            end = i;
        }
    }

    if (end != -1) return maxS;
    maxS = a[0];
    start = 0, end = 0;

    for (int i = 1; i < n; i++)
    {
        if (a[i] > maxS)
        {
            maxS = a[i];
            start = i, end = i;
        }
    }
    return maxS;
}

// calculate sum of rectangle from (x0, y0) to (x1, y1)
int sumRect(int x0, int y0, int x1, int y1)
{
    if (x0 <= x1 && y0 <= y1)
    {
        return pre[x1+1][y1+1] - pre[x0][y1+1] - pre[x1+1][y0] + pre[x0][y0];
    }
    return 0;
}

// find max sum rectangle
void maxRect(int m, int n)
{
    int maxS = INT_MIN;
    int l, r;
    int tmp1[m], s, start, end;

    for (l = 0; l < n; l++)
    {
        memset(tmp1, 0, sizeof(tmp1));

        for (r = l; r < n; ++r)
        {
            for (int i = 0; i < m; ++i)
            {
                tmp1[i] += arr[i][r];
            }
            s = kadane(tmp1, start, end, m);
            s -= sumRect(start+1, l+1, end-1, r-1);
            if (s > maxS && end - start + 1 >= 2 && r - l + 1 >= 2)
            {
                maxS = s;
            }
        }
    }

    int tmp2[n];
    for (l = 0; l < m; l++)
    {
        memset(tmp2, 0, sizeof(tmp2));

        for (r = l; r < m; ++r)
        {
            for (int i = 0; i < n; ++i)
            {
                tmp2[i] += arr[r][i];
            }
            s = kadane(tmp2, start, end, n);
            s -= sumRect(l+1, start+1, r-1, end-1);
            if (s > maxS && end - start + 1 >= 2 && r - l + 1 >= 2)
            {
                maxS = s;
            }
        }
    }

    // output
    cout << maxS;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // input
    int m, n;
    cin >> m >> n;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
        }
    }

    // prefix sum
    for (int i = 0; i <= m; i++)
    {
        pre[i][0] = 0;
    }
    for (int j = 0; j <= n; j++)
    {
        pre[0][j] = 0;
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + arr[i-1][j-1];
        }
    }

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + arr[i-1][j-1];
        }
    }

    maxRect(m, n);

    return 0;
}

赞(0）回复(0）举报 2023-05-19

我来回答

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

2条答案

相关问题

热门标签

最新问答