Hay una solución bastante clara para este problema. Voy a suponer que un triángulo debe estar hecho de 1s y aparecer como lo hizo en su ejemplo; creciendo hacia abajo y hacia la derecha. También supongo que está interesado en encontrar el triángulo más grande, ya que siempre hay un triángulo de tamaño 1.
Puede procesar la matriz fila por fila, haciendo un seguimiento para cada columna del triángulo más grande que se puede hacer en esta fila con esa columna como la esquina inferior izquierda. Puede inicializar esta matriz a todos los 0.
A medida que procesa cada fila, puede actualizar cada columna contando cuántos 1s hay comenzando desde esa columna hacia la derecha. Si hay X 1s y el triángulo más grande que se pudo hacer de la fila anterior en esta columna era el tamaño Y, entonces el triángulo más grande que se puede hacer en esta fila y columna es min (X, Y + 1). Puede actualizar todas las posiciones de la matriz con un paso lineal de la matriz de derecha a izquierda, rastreando cuántos 1s ha habido sin un 0.
- ¿Cuál es la nueva actualización del algoritmo de Google?
- ¿Cómo se realiza la reducción del tiempo polinómico de UHAMPATH a UHAMCYCLE?
- Cómo instalar la siguiente compresión tar.gz
- Cómo evaluar el efecto del programa de seguridad vial en el comportamiento después de 7 años de implementación si no hay datos de referencia
- ¿Existen algoritmos que estructuran datos previamente no estructurados utilizando 'etiquetas' definidas por el usuario?
El triángulo más grande que puedes hacer es el triángulo más grande que hayas encontrado.
