剑指offer42连续子数组的最大和

题目描述：//输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
// 要求时间复杂度为O(n)。
// 示例1:
// 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出: 6
//解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
// 提示：
// 1 <= arr.length <= 10^5
// -100 <= arr[i] <= 100
// Related Topics 分治算法 动态规划
解题思路：动态规划方法：
状态规划解析：
1.状态定义：设动态规划列表dp,dp[i]代表以元素num[i]为结尾的连续子数组最大和。
2.转移方程：若dp[i-1]<=0,说明dp[i-1]对dp[i]产生负贡献，即dp[i-1]+num[i]不如nums[i]本身大。
所以当dp[i-1]<=0时，即让dp[i]=nums[i];反正，dp[i-1]>0则说明对dp[i]有贡献，所以此时dp[i]=dp[i-1]+nums[i];
设定初始状态为：dp[0]=nums[0]。
返回值：返回dp列表中的最大值，代表全局最大值。
代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
               //设定初始值
             int res=nums[0];
              //遍历数组
             for (int i=1;i<nums.length;i++){
              //若数组i-1索引对应的值小于0时，即对dp[i]产生负贡献，
              //所以此时我们就直接取0，所以num[i]+=0;
                 nums[i]+=Math.max(nums[i-1],0);
              //
                 res=Math.max(res,nums[i]);
             }
             return res;
    }
}