Ravi de vous rencontrer tous. Mon nom est ryuichi69.
Aujourd'hui, je vais écrire la sortie de ce que j'ai étudié l'algorithme ici. Aujourd'hui, nous avons affaire à un algorithme appelé problème de sous-matrice maximum . S'il vous plaît laissez-nous savoir dans les commentaires s'il y a des parties difficiles à comprendre ou omission d'exigences.
Quel est le problème maximal de sous-matrice?
Eh bien, c'est le sujet principal. Le problème de la somme partielle maximale est un problème qui dit: " Il y a un tableau contenant des entiers dans chaque élément, et lorsque vous en sélectionnez certains, trouvez la valeur maximale du total de ceux sélectionnés ".
Problème
Soit
n un entier supérieur ou égal à 0. A ce moment, la séquence de nombres (tableau) a [k] constituée de n éléments satisfait les conditions suivantes.
De plus, soit k un entier naturel qui vérifie 1 ≤ k ≤ n. Sélectionnez n'importe quels k éléments de la séquence a [n]. Créez un programme dans lequel la somme des éléments sélectionnés à ce moment est S [k].
* Puisqu'il s'agit d'une pratique d'algorithme, nous ne considérons pas la quantité de calcul.
a = [7,9,-1,1,-4]
k = 4
* Si a = [7,9, -1,1] et les éléments du tableau ne sont pas dans l'ordre décroissant comme décrit ci-dessus, triez les éléments du tableau par ordre décroissant et total.
17
a = [-1,-2,-3,-4]
k = 3
* Si tous les éléments sont des entiers négatifs, ils ne seront pas ajoutés.
0
, ajoutez dans l'ordre de 0. Et si la valeur ajoutée totale est plus grande qu'avant l'addition, cette valeur est adoptée comme S_k . Plus précisément,
Programme Python
solve.php
# a[i]Pour organiser chaque élément de
#Bulle trier le tableau une fois
def bsort(arr):
#Pour remplacement
temp = 0
#Double boucle{Le montant du calcul est O(n^2)}
for i in range(0,len(arr)-1):
for j in range(0,len(arr)-1):
#Cette fois, c'est dans l'ordre décroissant, donc l'élément suivant provient de l'élément actuel
#Seulement s'il est grand, il sera remplacé.
if(arr[j] < arr[j+1]):
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
return arr
#Deux entiers a,Renvoie le plus grand de b
def max(a,b):
if a > b:
return a
return b
def solve(arr,k):
#Triez d'abord le tableau par ordre décroissant
b = bsort(arr)
#Méthode de planification dynamique(dp)Notez la valeur totale de chaque étape
dp = [0] * len(arr)
#Calculer dp{Le montant du calcul est O(n)}
for i in range(0,len(b)):
# dp[0](valeurinitiale)Decider
if i == 0:
#B si les éléments du tableau sont des entiers supérieurs à 0[0]
#Dp 0 si les éléments du tableau sont des entiers inférieurs à 0[0]Adoptez pour
#Puisqu'il est trié par ordre décroissant par tri à bulles, b[0] <Si 0
#Après cela, tout somme dp[i]Sera 0
dp[0] = max(b[0],0)
else:
# dp[i-1]+b[i]>dp[i-1]Uniquement dans le cas de dp[i]Adopté pour
#Sinon dp[i-1]Dp[i]Adopté pour
#Je suis désolé. Corrigée(2019.12.29)
dp[i] = max(dp[i-1]+b[i],dp[i-1])
#Dp correspondant au deuxième argument[k]rends le
return dp[k-1]
#pour le test
if __name__ == "__main__":
a = [7,9,-1,1,-4]
print(solve(a,4))
b = [-1,-2,-3,-4]
print(solve(b,3))
Référence
Ark's Blog | Kadane’s Algorithm |Problème de matrice partielle maximum
Qiita | Algorithme et structure de données en C # 1 ~ Problème maximal de tableau partiel ~