Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est de mettre en œuvre des fonctions et des classes spécifiques en fonction du thème.

En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.

Un site qui forme une puissance algorithmique capable de résister à des tests de codage dont on parle très tôt.

Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.

Leetcode

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 17 "169. Majority Element" à partir de zéro

En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.

problème

53. Maximum Subarray

Le niveau de difficulté est facile. L'une des 100 questions les plus appréciées.

Étant donné un tableau de nombres entiers uniquement nums. Le problème est de trouver un sous-tableau dans ce tableau qui a une somme maximale qui contient au moins un nombre et de renvoyer la somme.

Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6

Par exemple, si vous ajoutez tous les éléments consécutifs de nums [3] à nums [6], vous obtenez 4 + (-1) + 2 + 1 = 6, qui est la valeur maximale du tableau. Ce sera un calcul.

Solution

Je suis un amateur de Zub en matière de planification dynamique, mais je l'ai lu par hasard. [Structure des données et algorithme (nouvelle ingénierie du système de communication de l'information) (japonais)](https://www.amazon.co.jp/%E3%83%87%E3%83%BC%E3%82%BF% E6% A7% 8B% E9% 80% A0% E3% 81% A8% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0-% E6% 96% B0% E3% 83% BB% E6% 83% 85% E5% A0% B1-% E9% 80% 9A% E4% BF% A1% E3% 82% B7% E3% 82% B9% E3% 83% 86% E3% 83% A0% E5% B7% A5% E5% AD% A6-% E4% BA% 94% E5% 8D% 81% E5% B5% 90-% E5% 81% A5% E5% A4% AB / dp / 4901683497) [Organiser les modèles DP (méthode de planification dynamique) typiques Partie 1 ~ Knapsack DP ~](https://qiita.com/drken/items/a5e6fe22863b7992efdb#3-%E9%83%A8%E5%88 % 86% E5% 92% 8C% E5% 95% 8F% E9% A1% 8C% E3% 81% A8% E3% 81% 9D% E3% 81% AE% E5% BF% 9C% E7% 94% A8 % E3% 81% 9F% E3% 81% A1) Eh bien, il ne semble pas que cela puisse être résolu! ?? J'ai pensé, alors j'y ai pensé en y faisant référence.

Tout d'abord, préparez la valeur maximale «max_num» et la variable temporaire «temp». Remplacez les éléments du tableau de sorte qu'ils soient léchés depuis le début. Si temp est égal ou supérieur à 0, comparez-le avec max_num et temp, et le plus grand est assigné à max_num, sinon 0 est attribué à temp. Si vous essayez d'écrire un tel flux, ce sera comme suit.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        temp = 0
        max_num = max(nums)
        for i in range(len(nums)):
            temp += nums[i]
            if temp >= 0:
                max_num = max(max_num,temp)
            else:
                temp = 0
        return max_num
# Runtime: 60 ms, faster than 93.50% of Python3 online submissions for Maximum Subarray.
# Memory Usage: 14.5 MB, less than 5.69% of Python3 online submissions for Maximum Subarray.

Je n'ai pas beaucoup lu parce que j'avais une image que la méthode de planification dynamique était difficile à comprendre, mais quand je l'ai écrite, il semble que la mémoire puisse être rendue plus efficace et plus rapide, il semble donc préférable d'étudier à nouveau.

S'il y a une bonne réponse, je l'ajouterai.

[PYTHON] Soit Code Day18 à partir de zéro "53. Maximum Subarray"

Aperçu

problème

Solution