Hay una matriz amxn dada cada una con elementos enteros. El problema dice que tenemos que colocar dos torres en esa matriz, de manera que no se ataquen entre sí y la suma de los elementos sobre los que se colocan las torres sea máxima.
Ejemplo: Digamos que la matriz es
2 5 1 3Luego, las torres no atacantes se pueden colocar solo en posiciones de 2, 3 o 1, 5 elementos. Pero la suma máxima se encuentra en el caso de 1,5, por lo que la función debería devolver 1 + 5 = 6.
Pensé que podríamos revisar todos los pares de la matriz uno por uno y luego devolver la suma máxima que encontramos, pero parece que no puedo encontrar un enfoque mejor o más eficiente para esto. Mi solución sería O(m * m * n * n) en términos de complejidad.
¿Cuál sería un mejor enfoque? Apreciaría cualquier ayuda.
Para cada fila, encuentre los 2 valores principales y recuerde la columna donde se encontraron. O(mn)
Para cada columna, encuentre los 2 valores principales y recuerde la fila donde se encontraron. O(mn)
Las operaciones restantes, solo usamos las dos listas construidas anteriormente. No volveremos a mirar la matriz:
Para cada fila, pretenda colocar una torre en esa fila y en la columna con el valor más alto. Para cada columna, suma ese valor superior con el valor superior de la columna, excepto para la columna donde está la torre, donde sumamos con el segundo valor superior. Recuerda la fila de la torre imaginaria y la columna con la suma más alta. O(mn)
Repita, pero use el segundo valor más alto. O(mn)
Operación completa. O(mn) + O(mn) + O(mn) + O(mn) = O(mn)