算法1

$O(n)$

根据数组规律，使用两个参数
- max
- sum

max记录当前最大值
sum记录当前累加的数值

如果当前累加的数值比当前遍历的到的数小，则抛弃前面的数值，使得sum= nums[i]

然后判断max和累加的数值的关系，修改max

最终返回max即可

Java 代码

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums==null)
            return 0;
        int max = nums[0];
        int sum = nums[0];
        for(int i = 1 ; i<nums.length;i++){
            sum = sum + nums[i];
            if(sum<nums[i])
                sum = nums[i];
            if(max<sum)
                max = sum;
        }
        return max;
    }
}