剑指offer42

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

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

输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6

1. 动规题，cur记录下以当前索引位置为最右端的最大子数组。cur = Math.max(cur+nums[i],nums[i]);以当前索引位置为右端点的最大子数组中，当前索引位置左边的值之和一定为正数，否则只有它自身。