二维数组中的沙漏和

Question

我们得到一个 (6*6) 二维数组，我们必须在其中找到沙漏的最大和。例如，如果我们在一个全零的数组中使用数字 1 创建一个沙漏，它可能如下所示：

沙漏的总和是其中所有数字的总和。上面沙漏的总和分别是 7、4 和 2。

我为它编写了如下代码。这基本上是一个竞争性编程问题，由于我是该领域的新手，我编写的代码的复杂性非常差……也许程序无法产生所需的输出在规定的时间内。以下是我的代码：

     int main(){
    vector< vector<int> > arr(6,vector<int>(6));
    for(int arr_i = 0;arr_i < 6;arr_i++)
    {
      for(int arr_j = 0;arr_j < 6;arr_j++)
       {
        cin >> arr[arr_i][arr_j];
       }
    } //numbers input

    int temp; //temporary sum storing variable
    int sum=INT_MIN; //largest sum storing variable
    for(int i=0;i+2<6;i++) //check if at least3 exist at bottom
     {
       int c=0; //starting point of traversing column wise for row

       while(c+2<6) //three columns exist ahead from index
        {
          int f=0; //test case variable
          while(f!=1)
          { //if array does not meet requirements,no need of more execution

            for(int j=c;j<=j+2;j++)
             { //1st and 3rd row middle element is 0 and 2nd row is non 0.
               //condition for hourglass stucture
             if((j-c)%2==0 && arr[i+1][j]==0||((j-c)%2==1 && arr[i+1][j]!=0)
             //storing 3 dimensional subarray sum column wise
             temp+=arr[i][j]+arr[i+1][j]+arr[i+2][j]; //sum storage
             else
             f=1; //end traversing further on failure

              if(sum<temp)
              sum=temp;

              f=1;//exit condition
              }//whiel loop of test variable

             temp=0; //reset for next subarray execution
             c++; /*begin traversal from one index greater column wise till
                    condition*/
              }// while loop of c
        }
      }

          cout<<sum;

         return 0;
    }

这是我在时间间隔内无法处理的代码的实现。考虑到时间复杂度，请提出一个更好的解决方案，并随时指出我在理解问题方面的任何错误。问题来自 Hackerrank。如果您仍然需要，这里是链接： https ://www.hackerrank.com/challenges/2d-array

原文由 Sarthak Mehra 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您的问题的解决方案是：

 #include <cstdio>
#include <iostream>
#include <climits>

int main() {
    int m[6][6];

    // Read 2D Matrix-Array
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            std:: cin >> m[i][j];
        }
    }

    // Compute the sum of hourglasses
    long temp_sum = 0, MaxSum = LONG_MIN;
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            if (j + 2 < 6 && i + 2 < 6) {
                temp_sum = m[i][j] + m[i][j + 1] + m[i][j + 2] + m[i + 1][j + 1] + m[i + 2][j] + m[i + 2][j + 1] + m[i + 2][j + 2];
                if (temp_sum >= MaxSum) {
                    MaxSum = temp_sum;
                }
            }
        }
    }
    fprintf(stderr, "Max Sum: %ld\n", MaxSum);

    return 0;
}

该算法很简单，它将所有从左上角开始的沙漏相加，最后2列和2行不处理，因为它不能形成沙漏。

原文由 chema989 发布，翻译遵循 CC BY-SA 3.0 许可协议