Kadane Algorithim
1.0.0
Dies ist eine JavaScript -Lösung für einen der berühmten dynamischen Programme Algo Kadanes Algorithim.
Dieses YouTube-Video von Ben Wright könnte nützlich sein, um den Kadane-Algorithmus für die maximale Subtarray in einer 1-D-Sequenz zu verstehen.
Die erste Zeile des Eingangs verfolgt eine Ganzzahl -T. t -Fälle. Jeder Testfall beginnt mit einer Ganzzahl N. In der nächsten Zeile folgen N -Zahlen, die die Elemente von Array A darstellen.
1 ≤ T ≤ 10
1 ≤ N ≤ 105
–104 ≤ai ≤ 104
Die von Ihnen in Betracht gezogene Subtarray und Untersequenzen sollten mindestens ein Element haben.
Zwei, der Raum trennte sich, Ganzzahlen, die das maximale zusammenhängende und nicht kontiouöse Subarray bezeichnen. Mindestens eine Ganzzahl sollte ausgewählt und in die Subtarrays gesteckt werden (dies kann in Fällen erforderlich sein, in denen alle Elemente negativ sind).
2
4
1 2 3 4
6
2 -1 2 3 4 -5
10 10
10 11
Im ersten Fall: Die maximale Summe sowohl für zusammenhängende als auch für nicht verknüpfte Elemente ist die Summe aller Elemente (da sie alle positiv sind).
Im zweiten Fall: [2 -1 2 3 4] -> Dies bildet das zusammenhängende Unterarray mit der maximalen Summe. Fügen Sie für die maximale Summe einer nicht notwendigerweise übereinstimmenden Gruppe von Elementen einfach alle positiven Elemente hinzu.
