給定一個數組,求數組中最大連續子序列的和

時間複雜度為O(n)

#只需要過一遍陣列即可，但是需要深入理解這個陣列的本質特徵，即動態規劃的方法。

先設定兩個變量，thisSum和maxSum。其中thisSum表示走到目前位置元素的和；maxSum表示走到目前位置下的連續子序列的最大和。

注意：如果thisSum為負，則直接將其置為0；如果thisSum大於maxSum，則將maxSum置為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;
    }

推薦教學：PHP教學

以上是給定一個數組,求數組中最大連續子序列的和的詳細內容。更多資訊請關注PHP中文網其他相關文章！