Trouver une sous-matrice avec la somme maximale possible dans O (n^2)

Question

J'essaye d'écrire un programme en Java qui, lorsqu'on lui donnera une matrice MxN, trouvera la sous-matrice (contiguë) avec la plus grande somme de nombres. Le programme doit ensuite retourner les coordonnées du coin supérieur gauche de la sous-matrice et les coordonnées du coin inférieur droit. La matrice peut inclure des nombres négatifs et la matrice et la sous-matrice n'ont pas besoin d'être carrées.

J'ai vu que cela a été discuté ici: Getting the submatrix with maximum sum? et la solution semble être O (n^3). Un de mes amis a dit qu'ils avaient déjà réussi à résoudre ce problème en O (n^2). Aussi suggéré here. Est-ce possible?

Existe-t-il un code disponible qui résout ce problème de la manière la plus efficace?

Answer 1

Vous (probablement) ne pouvez pas résoudre votre problème dans O(n^2), au moins un tel algorithme n'est pas connu. La solution optimale a une complexité sous-cubique, mais elle est très difficile à mettre en œuvre et probablement plus lente dans la pratique. Vous pouvez lire un article à ce sujet here.

L'algorithme habituel utilisé est le O(n^3) référencé dans la question que vous avez trouvée.

Answer 2

solution

(S) Il est un de vos amis .. si juste lui demander/elle, et faire partager avec nous aussi :)