c++ - 二维数组中的沙漏总和

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

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行不处理，因为不能形成沙漏。