[Python] Soma Máxima de Sub-matriz Retangular: Força Bruta O(N^6) e Alternativas [fechada]

Estou resolvendo um problema relacionado a soma de um maxima de sub array. Fiz o código força bruta, onde passa por todas as linhas e colunas de uma matriz nxn e depois pega a soma atual e a soma maxima e vê qual é o maior.

n = matriz.shape[0]

max_soma = matriz[0][0]

for linha1 in range(n):
for linha2 in range(linha1, n):
for coluna1 in range(n):
for coluna2 in range(coluna1, n):
soma_momento = 0

for i in range(linha1, linha2 + 1):
for j in range(coluna1, coluna2 + 1):
soma_momento += matriz[j]
max_soma = max(max_soma, soma_momento)
return max_soma



Quero saber se existe alguma outra variação ou implementação do algoritmo de força bruta para este problema que ainda mantenha uma complexidade de tempo não otimizada (como O(N^6) ou O(N^5)), para fins de comparação didática, sem usar otimizações como Somas de Área Pré-calculadas (O(N^4)) ou Kadane 2D (O(N^3)).

Continue reading...