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

時間複雜度為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教學

以上就是給定一個陣列,求陣列中最大連續子序列的和的詳細內容，更多請關注TW511.COM其它相關文章！