Решил задачу, сам написал алгоритм, понятно что сложность высока, алгоритм обходит матрицу очень много раз, но должен работать на мой взгляд. На тестовых данных выдаёт правильные результаты. А валидатор говорит таймаут. Объясните почему таймаут? Бесконечных циклов то в программе нет.
package com.javarush.task.task39.task3912;
/*
Максимальная площадь
*/
public class Solution {
public static void main(String[] args) {
int[][] matrix = {
{0, 1, 1, 1, 1},
{1, 0, 1, 0, 1},
{1, 1, 1, 1, 1},
{1, 0, 1, 1, 1},
{1, 1, 1, 1, 0},
};
System.out.println(Solution.maxSquare(matrix));
int[][] matrix2 = new int[][]{
{ 1, 1, 1, 1, 0, 1, 0, 0, 1, 1 },
{ 1, 0, 1, 1, 0, 1, 0, 0, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 0, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 1, 1, 1, 1, 1, 1 },
{ 0, 1, 1, 0, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 0, 1, 0, 1, 1, 1 }
};
System.out.println(maxSquare(matrix2));
}
public static int maxSquare(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int maxSizeSquare = 0;
for (int i = 0; i < matrix.length - 1; i++) {
for (int j = 0; j < matrix[0].length - 1; j++) {
if (matrix[i][j] == 1) {
int currentSizeSquare = countSizeSquare(matrix, i, j);
if (currentSizeSquare > maxSizeSquare) {
maxSizeSquare = currentSizeSquare;
}
}
}
}
return maxSizeSquare*maxSizeSquare;
}
public static int countSizeSquare(int[][] matrix, int startI, int startJ) {
int sizeSquare = 1;
int bound = Math.min(matrix.length - startI , matrix[0].length - startJ )-1;
for (int i = 1; i <= bound; i++) {
boolean fullSquare = true;
// обход квадрата размером от startI + i , startJ + i на проверку каждого значения 1
int maxI = startI + i+1;
int maxJ = startJ + i+1;
for (int x = startI; x < maxI; x++) {
for (int y = startJ; y < maxJ; y++) {
if (matrix[x][y] != 1){
fullSquare = false;
}
}
}
if (fullSquare) {
sizeSquare = i+1;
}
}
return sizeSquare;
}
}