Ermitteln Sie bei einem gegebenen Array die Summe der größten aufeinanderfolgenden Teilsequenzen im Array

Die Zeitkomplexität ist O(n)

Sie müssen das Array nur einmal durchgehen, aber Sie müssen das Wesentliche tiefgreifend verstehen Eigenschaften dieses Arrays. Das heißt, die Methode der dynamischen Programmierung.

Legen Sie zunächst zwei Variablen fest, thisSum und maxSum. Unter diesen stellt thisSum die Summe der Elemente dar, die die aktuelle Position erreichen; maxSum stellt die maximale Summe aufeinanderfolgender Teilsequenzen dar, die die aktuelle Position erreichen.

Hinweis: Wenn thisSum negativ ist, setzen Sie es direkt auf 0; wenn thisSum größer als maxSum ist, setzen Sie maxSum auf den Wert von thisSum.

public static int maxSubArray(int[] nums)
    {
        int length = nums.length;
        if(length <= 0)
            return 0;
        int CurSum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < length; i++)
        {
            if(CurSum <= 0)     //当当前的和小于等于0，那么就给其置为当前元素的值
                CurSum = nums[i];
            else
                CurSum += nums[i];
            if(CurSum > max)
                max = CurSum;
        }
        return max;
    }

Empfohlenes Tutorial: PHP-Tutorial

Das obige ist der detaillierte Inhalt vonErmitteln Sie bei einem gegebenen Array die Summe der größten aufeinanderfolgenden Teilsequenzen im Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!