最大子数组和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

动态规划类：
只有1个元素的话，那肯定就是这个元素。
增加1个元素后，如何与原来的小规模问题关联？

假定为数组a
c[i]代表以a[i]结尾的，连续子数组的最大和。
c[i]=max{c[i-1]+a[i],a[i]}

class Solution {
    public int maxSubArray(int[] nums) {
        //分解子问题
        int res = nums[0];
        for(int i = 1;i< nums.length;i++){
            if(nums[i-1]>0){
                nums[i] += nums[i-1];
            }
            if(res < nums[i]){
                res = nums[i];
            }

        }
        return res;

    }
}