Kadanes Algorithmus: Leetcode Maximales Subarray

Intuition

Wir können die Intuition basierend auf dem Zwei-Punkte-Ansatz aufbauen.

Ansatz

Wir beginnen mit zwei Variablen maxSum und maxTillNow.

• Die erste Variable speichert die maximale Summe, die wir insgesamt im Array erreicht haben.

• Die zweite Variable speichert den Wert der maximalen Summe, die bis zum aktuellen Index erreicht wurde. Da das Array einen negativen Wert hat, schwankt dieser Wert, aber wann immer wir maxSum < maxTillNow aktualisieren wir die maxSum.

• Der letzte Fall, den wir behandeln müssen, ist, wenn die maximale Summe bis zu einem Index Null erreicht, d. h. maxTillNow < 0, setze maxTillNow = 0 am Ende der Schleife zurück.

Komplexität

• Zeitliche Komplexität: O(N)

• Raumkomplexität: O(1)

Code

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int maxTillNow = 0;
        for(int i =0;i<nums.length;i++){
            maxTillNow+=nums[i];
            maxSum = Math.max(maxTillNow,maxSum);
            if(maxTillNow<0) maxTillNow = 0;
        }
        return maxSum;
    }
}

GitHub-Repo für weitere Lösungen: Git
Leetcode-Profil: Leetcode: devn007

Das obige ist der detaillierte Inhalt vonKadanes Algorithmus: Leetcode Maximales Subarray. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!