Hackerrankから砂時計プログラムを最適化するにはどうすればよいですか？

Question

これはHackerrankのウェブサイトにある砂時計の問題です。

public class Solution 
    { 
    public static int hourglass(int[][] a, int n) 
    { 
     int max = -999; 
     for (int i = 0; i < n; i++) 
     {   
      for (int j = 0; j < n; j++) 
      { 
       int sum = 0; 
       boolean flag = false; 

       if ((i+2) < n && (j+2) < n) 
       { 
        sum += a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j+1] + a[i+2][j] + a[i+2][j+1] + a[i+2][j+2]; 
        flag = true; 
       } 
       if (sum > max && flag == true) 
        max = sum; 
      } 
     } 
     return max; 
    } 
    public static void main(String[] args) 
    { 
     Scanner scanner = new Scanner(System.in); 
     int n = 6; 
     int[][] a = new int[6][6]; 

     for (int i = 0; i < n; i++) 
      for (int j = 0; j < n; j++) 
       a[i][j] = scanner.nextInt(); 

     int maxSum = hourglass(a, n); 
     System.out.println(maxSum); 
    } 
} 

私の質問今

、上記のコード：Hourglass

ここで私が砂時計の問題のために書いたコードは次のとおりです。ここで

は、問題へのリンクがありますコンパイルして正常に実行し、すべてのテストケースに合格しました。しかし、私のコードはO（n^2）時間（ここでは行列のサイズは6ですが、サイズがnならばO（n^2）時間がかかります）

O（n^2）の時間をかけて配列を作成し、私は心配していません。私が興味を持っているのは、砂時計の合計を計算するのにO（n^2）時間がかかる砂時計（）メソッドを最適化することです。

したがって、さらに最適化して上記の問題を実装する方法はありますか？

O（n）時間の問題を解決することは可能ですか？

実際には、hourglass（）メソッドで内部ループを削除してO（n）時間の問題を解決しようとしましたが、動作していないようです。

P.S.私は動作可能なコードは必要ありません。必要なのは、可能な改善点（もしあれば）やアルゴリズムに関するポインタです。

ありがとうございます！

Answer 1

技術的には、解決策はすでにO（n）です。あなたは2d配列の片側であるかのように "n"を定義していますが、nをボード上のユニークな配置と見なした場合、nはrow * colの組み合わせです。このように定義し直すと、この問題でO（n）を打ち負かすことはできません。

ただし、一部を最適化することはできます。基本的に6x6ボードに3x3タイルを敷き詰めています。プレースメントを3x3タイルの左上隅で定義する場合は、36個のプレースメントすべてを試しています。あなたがそれについて考えるなら、それらの配置の多くはあなたのタイルをボードの端から垂らしておくでしょう。実際には、すべての6x6ポジションではなく、最初の4x4ポジションを考慮する必要があります。これはまだO（n）の解決策ですが、36回の繰り返しを16回まで減らすことができます。