[PYTHON] Lassen Sie Code Day18 ab Null "53. Maximum Subarray"

Überblick

Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.

Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.

Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.

Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.

Leetcode

Leet Code-Tabelle ab Null

Letztes Mal Leet Code Tag 17 "169. Mehrheitselement" ab Null

Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.

Problem

53. Maximum Subarray

Der Schwierigkeitsgrad ist einfach. Eine der 100 beliebtesten Fragen.

Angesichts des Nur-Ganzzahl-Arrays nums. Das Problem besteht darin, ein Unterarray in diesem Array mit einer maximalen Summe zu finden, die mindestens eine Zahl enthält, und die Summe zurückzugeben.

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

Wenn Sie beispielsweise alle aufeinander folgenden Elemente von "nums [3]" zu "nums [6]" hinzufügen, erhalten Sie 4 + (-1) + 2 + 1 = 6, was dem Maximalwert im Array entspricht. Es wird eine Berechnung sein.

Lösung

Ich bin ein Zub-Amateur über dynamische Planung, aber ich habe es zufällig gelesen. [Datenstruktur und Algorithmus (neues Engineering von Informationskommunikationssystemen) (Japanisch)](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) [Organisieren Sie typische DP-Muster (Dynamic Planning Method) Teil 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) Nun, es sieht nicht so aus, als ob es gelöst werden kann! ?? Ich dachte, also dachte ich darüber nach, während ich mich darauf bezog.

Bereiten Sie zunächst den Maximalwert "max_num" und die temporäre Variable "temp" vor. Ersetzen Sie die Elemente des Arrays so, dass sie von Anfang an geleckt werden. Wenn "temp" 0 oder mehr ist, vergleichen Sie es mit "max_num" und "temp", das größere wird "max_num" zugewiesen, andernfalls " 0 ist temp` zugeordnet. Wenn Sie versuchen, einen solchen Ablauf zu schreiben, sieht dieser wie folgt aus.

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.

Ich habe nicht viel gelesen, weil ich ein Bild hatte, das die dynamische Planungsmethode schwer zu verstehen war, aber als ich es schrieb, schien es, dass das Gedächtnis effizienter und schneller gemacht werden kann, so dass es besser scheint, wieder hart zu lernen.

Wenn es eine gute Antwort gibt, werde ich sie hinzufügen.

Recommended Posts

Lassen Sie Code Day18 ab Null "53. Maximum Subarray"
Lassen Sie Code Day49 ab Null "1323. Maximum 69 Number".
Lassen Sie Code Day16 von vorne beginnen "344. Reverse String"
Lassen Sie Code Day89 "62. Unique Paths" ab Null
Lassen Sie Code Tag 55 "22. Klammern erzeugen" ab Null
Lassen Sie Code Tag 13 "338. Bits zählen" ab Null
Lassen Sie Code Day71 ab Null "1496. Pfadkreuzung"
Lassen Sie Code Tag 61 "7. Reverse Integer" ab Null
Lassen Sie Code Tag 82 "392. Ist Folge" ab Null
Lassen Sie Code Day51 "647. Palindromic Substrings" ab Null
Lassen Sie Code Tag 50 "739. Tägliche Temperaturen" ab Null
Lassen Sie Code Day15 ab Null "283. Nullen verschieben"
Lassen Sie Code Day14 ab Null "136. Single Number"
Lassen Sie Code Day7 ab Null "104. Maximale Tiefe des Binärbaums"
Lassen Sie Code Day 43 von vorne beginnen "5. Längster palindromischer Teilstring"
Lassen Sie Code Day74 ab Null "12. Integer to Roman"
Lassen Sie Code Day57 ab Null "35. Search Insert Position"
Lassen Sie Code Day47 von vorne beginnen "14. Längstes gemeinsames Präfix"
Lassen Sie Code Day78 von vorne beginnen "206. Reverse Linked List"
Lassen Sie Code Day75 von vorne beginnen "15.3 Sum"
Lassen Sie Code Day 44 "543. Durchmesser des Binärbaums" von vorne beginnen
Lassen Sie Code Tag 64 ab Null "287. Finden Sie die doppelte Nummer"
Lassen Sie Code Day 31 von vorne beginnen "581. Kürzestes unsortiertes kontinuierliches Subarray"
Lassen Sie Code Day 84 ab Null "142. Linked List Cycle II"
Lassen Sie Code Day 29 "46. Permutationen" von vorne beginnen
Lassen Sie Code Day24 ab Null "21. Zwei sortierte Listen zusammenführen"
Lassen Sie Code Day12 von vorne beginnen "617. Zwei binäre Bäume zusammenführen"
Lassen Sie Code Day2 von vorne beginnen "1108. IP-Adresse löschen"
Lassen Sie Code Day70 ab Null "295. Median aus Datenstrom suchen"
Lassen Sie Code Day81 "347. Top K Frequent Elements" ab Null
Lassen Sie Code Day 65 "560. Subarray Sum Equals K" von vorne beginnen
Lassen Sie Code Day48 ab Null "26. Duplikate aus sortiertem Array entfernen"
Lassen Sie Code Day87 ab Null "1512. Anzahl der guten Paare"
Lassen Sie Code Day67 von vorne beginnen "1486. XOR-Operation in einem Array"
Lassen Sie Code Day56 ab Null "5453. Laufende Summe von 1d Array"
Lassen Sie Code Day86 ab Null "33. Suche in gedrehtem sortiertem Array"
Lassen Sie Code Day5 ab Null "1266. Mindestzeit für den Besuch aller Punkte"
Lassen Sie Code Tag 35 "160. Schnittpunkt zweier verknüpfter Listen" von vorne beginnen
Lassen Sie Code Day83 ab Null "102. Order Traversal auf Binäre Baumebene"
Lassen Sie Code Day 41 "394. Decode String" ab Null
Lassen Sie Code Day 25 "70. Climbing Stairs" von vorne beginnen
Lassen Sie die Codetabelle von Null beginnen
Lassen Sie Code Day69 von vorne beginnen "279. Perfect Squares"
Lassen Sie Code Day 34 von vorne beginnen "118. Pascals Dreieck"
Lassen Sie Code Day85 von vorne beginnen "6. Zick-Zack-Konvertierung"
Lassen Sie Code Day20 von vorne beginnen "134. Tankstelle"
Lassen Sie Code Day 88 "139. Word Break" von vorne beginnen
Lassen Sie Code Day 28 "198. House Robber" von vorne beginnen
Lassen Sie Code Day 39 "494. Target Sum" von vorne beginnen
Lassen Sie Code Day 36 "155. Min Stack" von vorne beginnen
Lassen Sie Code Tag 17 "169. Mehrheitselement" von vorne beginnen
Lassen Sie Code Tag 33 "1. Zwei Summe" ab Null
Lassen Sie Code Tag 40 ab Null "114. Binärbaum auf verknüpfte Liste reduzieren"
Lassen Sie Code Tag 91 "153. Minimum in gedrehtem sortiertem Array finden" ab Null
Lassen Sie Code Day59 ab Null "1221. Teilen Sie einen String in ausgeglichene Strings"
Lassen Sie Code Tag 11 ab Null "1315. Summe der Knoten mit gleichwertigen Großeltern"
Lassen Sie Code Day6 ab Null beginnen "1342. Anzahl der Schritte, um eine Zahl auf Null zu reduzieren"
Lassen Sie Code Tag 23 "226. Binären Baum umkehren" von vorne beginnen
Lassen Sie Code Day8 ab Null "1302. Deepest Leaves Sum"
Lassen Sie Code Tag 22 ab Null "141. Linked List Cycle"
Lassen Sie Code Day 32 "437. Path Sum III" von vorne beginnen