Résolvez le problème maximum de sous-tableau en Python

Introduction

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.

  1. a [0], a [1], ..... a [n-1] est un entier
  2. On suppose que chaque élément de la séquence a est arrangé par ordre décroissant. .. Pour tous les nombres naturels i qui satisfont 1 ≤ i ≤ (n-1), a [i]> a [i + 1] est satisfait.

    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].

    Contraintes
    1. 1≦n≦10
    2. 1≦k≦10
    3. -10≦a[k]≦10

    * Puisqu'il s'agit d'une pratique d'algorithme, nous ne considérons pas la quantité de calcul.

    Entrée 1

    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.

    Sortie 1

    17

    Entrée 2

    a = [-1,-2,-3,-4]
    k = 3
    * Si tous les éléments sont des entiers négatifs, ils ne seront pas ajoutés.

    Sortie 2

    0

    Comment faire (algorithme de Kadane) Pour chaque séquence

    , 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,

    1. Trier le tableau par ordre décroissant
    2. Créer une fonction max (a, b) qui renvoie le plus grand des entiers a et b
    3. Augmenter k de 1. Allez ajouter un [k] à la valeur de somme maximale s [k-1], considérez les cas où ils ne sont pas ajoutés, et notez (stockez) dans le tableau avec la plus grande valeur comme s [k]. (Méthode de planification dynamique). Exprimé dans la formule,