刷LeetCode 53題的時(shí)候，想不出來(lái)O(n)復(fù)雜度的解，上網(wǎng)去搜，發(fā)現(xiàn)了這個(gè)算法，專門來(lái)求最大子序列的和，算法就是考慮，數(shù)組中的A[I]前面的的序列段的和為sum，如果sum大于等于零，那么加上A[i]，如果sum小于零，就沒(méi)有必要加了，不如直接保留A[i]，這樣就相當(dāng)于從A[i]開(kāi)始的一個(gè)新的數(shù)字段。保留一個(gè)max保存最大的值，每次都和max比較。

class Solution {
        public int maxSubArray(int[] nums) {
            int max = Integer.MIN_VALUE, sum = 0;
            for (int i = 0;i < nums.length; i++) {
                if (sum <= 0) sum = nums[i];
                else sum = sum + nums[i];
                if (max < sum) max = sum;

            }
            return max;
        }
    }