/*
1. 状态定义: f[i] 是以i结尾的连续子数组最大和
2. 状态计算: 以i为最后一个数字划分, 
2.1 与之前的数组一起构成新数组 -> f[i] + f[i-1]
2.2 自己构成新数组 -> f[i]
2.3 f[i] = max(f[i], f[i-1] + f[i])
3. 边界条件: f[0] = nums[0];
*/


class Solution {
    public int maxSubArray(int[] nums) {
        for (int i = 1; i < nums.length ; i ++)
            nums[i] = Math.max(nums[i], nums[i] + nums[i-1]);
        return Arrays.stream(nums).max().getAsInt();
    }
}