Voici une explication pour aller avec le posté code. Il y a deux trucs à faire ce travail efficacement: (I) Kandane de l'algorithme et (II) à l'aide du préfixe sommes. Vous devez également (III) appliquer les astuces de la matrice.
Partie I: Kandane de l'algorithme de
Kandane de l'algorithme est un moyen de trouver une ligne de sous-suite avec le maximum de la somme. Permet de commencer avec une approche par force brute pour trouver le max contigus sous-suite et ensuite pensez à optimiser pour obtenir Kandane de l'algorithme.
Supposons que vous disposez de la séquence:
-1, 2, 3, -2
Pour l'approche par force brute, marcher le long de la séquence de générer tous les possible de sous-séquences comme indiqué ci-dessous. En considérant toutes les possibilités, on peut commencer, prolonger, ou à la fin une liste avec chaque étape.
At index 0, we consider appending the -1
-1, 2, 3, -2
^
Possible subsequences:
-1 [sum -1]
At index 1, we consider appending the 2
-1, 2, 3, -2
^
Possible subsequences:
-1 (end) [sum -1]
-1, 2 [sum 1]
2 [sum 2]
At index 2, we consider appending the 3
-1, 2, 3, -2
^
Possible subsequences:
-1, (end) [sum -1]
-1, 2 (end) [sum -1]
2 (end) [sum 2]
-1, 2, 3 [sum 4]
2, 3 [sum 5]
3 [sum 3]
At index 3, we consider appending the -2
-1, 2, 3, -2
^
Possible subsequences:
-1, (end) [sum -1]
-1, 2 (end) [sum 1]
2 (end) [sum 2]
-1, 2 3 (end) [sum 4]
2, 3 (end) [sum 5]
3, (end) [sum 3]
-1, 2, 3, -2 [sum 2]
2, 3, -2 [sum 3]
3, -2 [sum 1]
-2 [sum -2]
Pour cette approche par force brute, nous avons enfin chercher la liste avec le meilleur de la somme, (2, 3), et c'est la réponse. Cependant pour faire de cette efficace, considérez que vous n'avez pas vraiment besoin de garder tous l'une des listes. Sortir des listes qui n'ont pas terminé, vous avez seulement besoin de garder le meilleur, les autres ne peuvent pas faire mieux. Sortir des listes qui se sont terminées, vous ne pourriez avoir besoin de garder le meilleur, et seulement si elle est meilleure que celles qui ne l'ont pas terminé.
Ainsi, vous pouvez garder une trace de ce que vous avez besoin avec juste une position de tableau et une somme de tableau. La position de la matrice est définie comme ceci: position[r] = s conserve la trace de la liste qui se termine à la r et commence à s. Et, somme[r] donne de la somme pour la sous-suite qui se termine à l'indice de r. C'est l'approche optimisée est Kandane de l'algorithme.
Cours d'exécution à travers l'exemple de nouveau en gardant la trace de nos progrès, de cette façon:
At index 0, we consider appending the -1
-1, 2, 3, -2
^
We start a new subsequence for the first element.
position[0] = 0
sum[0] = -1
At index 1, we consider appending the 2
-1, 2, 3, -2
^
We choose to start a new subsequence because that gives a higher sum than extending.
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
At index 2, we consider appending the 3
-1, 2, 3, -2
^
We choose to extend a subsequence because that gives a higher sum than starting a new one.
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
position[2] = 1 sum[2] = 5
Again, we choose to extend because that gives a higher sum that starting a new one.
-1, 2, 3, -2
^
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
position[2] = 1 sum[2] = 5
positions[3] = 3 sum[3] = 3
Encore une fois, le meilleur de la somme est 5 et la liste est à partir de l'index 1 index 2, qui est (2, 3).
Partie II: Préfixe sommes
Nous voulons avoir un moyen de calculer la somme, le long d'une ligne, pour n'importe quel point de départ de tout point de fin. Je veux calculer la somme en O(1) temps plutôt que de simplement ajouter, qui prend O(m) temps où m est le nombre d'éléments dans la somme. Avec quelques precomputing, cela peut être obtenue. Voici comment. Supposons que vous disposez d'une matrice:
a d g
b e h
c f i
Vous pouvez précalculer cette matrice:
a d g
a+b d+e g+h
a+b+c d+e+f g+h+i
Une fois que c'est fait, vous pouvez obtenir la somme de courir le long d'une colonne à partir du tout début à la fin, point dans la colonne juste par soustraction de deux valeurs.
Partie III: Apporter des trucs ensemble pour trouver le max submatrix
Supposons que vous savez le haut et le bas de ligne du max submatrix. Vous pouvez faire ceci:
- Ignorer les lignes au-dessus de votre rangée du haut, et ignorer les lignes en dessous de votre fond
ligne.
- Avec ce que la matrice reste, envisager l'utilisation de la somme de chaque colonne pour
forme d'une séquence (un peu comme une ligne qui représente plusieurs lignes).
(Vous pouvez calculer n'importe quel élément de cette séquence rapide avec le préfixe
sommes approche.)
- Utilisation Kandane l'approche de la figure mieux en sous-suite dans ce
la séquence. Les indices que vous obtiendrez vous dire la gauche et la droite
les positions de la meilleure submatrix.
Maintenant, quelle est effectivement déterminer le haut et le bas de ligne? Juste essayer toutes les possibilités. Essayez de mettre le haut partout où vous le pouvez et de mettre le bas n'importe où vous le pouvez, et exécuter la Kandane-base de la procédure décrite précédemment pour chaque possibilité. Lorsque vous trouvez un max, vous de garder le haut et le bas de la position.
Trouver la ligne et la colonne prend O(M^2) où M est le nombre de lignes. Trouver la colonne prend O(N) le temps où N est le nombre de lignes. Donc, le temps total est O(M^2 * N). Et, si M=N, le temps est O(N^3).
