Kadanes Algorithm
Verfasst: Dienstag 23. März 2021, 17:16
Given an array of positive integers nums, return the maximum possible sum of an ascending subarray in nums.
A subarray is defined as a contiguous sequence of numbers in an array.
A subarray [numsl, numsl+1, ..., numsr-1, numsr] is ascending if for all i where l <= i < r, numsi < numsi+1. Note that a subarray of size 1 is ascending.
Input: nums = [10,20,30,5,10,50] Output: 65 Explanation: [5,10,50] is the ascending subarray with the maximum sum of 65.
Ich versuche das mit Kadanes Algorithmus zu machen. Meine Liste sieht dann so aus [10,30,60,65,75,125] . Ich verstehe nicht warum der output nur die letzten 3 Elemente der Liste ausgibt und nicht die letzen 4 oder 5 dann ist das Ergebnis noch größer. [20,30,5,10,50] wäre doch größer als [5,10,50]. Kann man natürliche Zahlen mit Kadanes Algorithmus lösen?
A subarray is defined as a contiguous sequence of numbers in an array.
A subarray [numsl, numsl+1, ..., numsr-1, numsr] is ascending if for all i where l <= i < r, numsi < numsi+1. Note that a subarray of size 1 is ascending.
Input: nums = [10,20,30,5,10,50] Output: 65 Explanation: [5,10,50] is the ascending subarray with the maximum sum of 65.
Ich versuche das mit Kadanes Algorithmus zu machen. Meine Liste sieht dann so aus [10,30,60,65,75,125] . Ich verstehe nicht warum der output nur die letzten 3 Elemente der Liste ausgibt und nicht die letzen 4 oder 5 dann ist das Ergebnis noch größer. [20,30,5,10,50] wäre doch größer als [5,10,50]. Kann man natürliche Zahlen mit Kadanes Algorithmus lösen?