最大の子マトリックスを探す

今日のお題

各セルに1か0が入った長方形が、String[]で与えられる。その長方形の中で、1だけで満たされた最大の長方形を探し、その面積（すなわち1の数）を返すメソッドを書け。

回答

import java.util.*; 
import java.io.*;

class Main {  
  public static String MaximalSquare(String[] strArr) { 

    int rowLen = strArr.length;
    int colLen = strArr[0].length();
    int maxLen = rowLen < colLen ? rowLen : colLen;
    
    int len = maxLen;
    for(; 0 <= len; len--){
        for(int row = 0; row <= rowLen-len; row++){
            for(int col = 0; col <= colLen - len; col++){
                boolean found = false;
                if(strArr[row].charAt(col) == '1'){
                    found = true;
                    for(int i = 1; i < len; i++){
                        if(strArr[row].charAt(col+i) != '1'){
                            found = false;
                        }
                    }
                }
                
                //start searching submatrix of size len from (row,col)
                if(found){
                    boolean subFound = true;
                    for(int y = row + 1; y < row + len; y++){
                        for(int x = col; x < col + len; x++){
                            if(strArr[y].charAt(x) != '1'){
                                subFound = false;
                            }
                        }
                    }
                    if(subFound){
                        return Integer.toString(len*len);
                    }
                }
            }
        }
    }

    return "0";
  }
  
  //Coderbyteのお作法
  public static void main (String[] args) {  
    // keep this function call here     
    //Scanner s = new Scanner(System.in);
    System.out.println(MaximalSquare(new String[] {"0111", "1101", "0111"})); 
    System.out.println(MaximalSquare(new String[] {"0111", "1111", "1111", "1111"}));
  }
}

感想

問題を聞いて単純な探索アルゴリズムはすぐに思いつくのだが、配列の脳みそが劣化していてインデックス操作をいくつも間違えてしまい、面倒くさくなってデバッガで追い込む結果となった。O(n²)？だけど、きっともっとうまいアルゴリズムがあるのだろう。回答者（正答者？）がグッと減って、回答例は1個しか表示されず、その人も同じような方針で解いていた。