variante du plus grand block de 1 dans une matrice

Hello tout le monde. J ai reussi à resoudre le problème avec la programmation dynamique qui etant donné une matrice binaire tel :

1110
1100
1100
1000

Doit trouver le plus grand carré de 1 en o(n^2).
Seulement maintenant, on me demande ceci :
Si on vous donne les coordonnées d'au moins un 1 dans la matrice, pouvez-vous donner un algo en theta(n) qui nous donne le plus grand carré de 1?? Justifiez

J ai penser à du divide and conquer, utiliser les.diagonales etc.. mais je bloque vraiment.
Merci de m'aidé.

J apporte une précision : l'agencement des 1 dans la matrice suit une propriété :
Si on trace un segment ( horizontal ou vertical ) entre deux cases contenant un 1, alors toutes les cases par lesquelles passent le segment sont des 1.
Merci d m aider ..