今日题目（剑指Offer系列）
剑指 Offer 42. 连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。 求所有子数组的和的最大值。 要求时间复杂度为O(n)。
示例：
输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
解题思路：
>本题目要求是求多个连续子数组的最大值 >所以考虑使用动态规划 >我们可以用dp[i]代表每个位置以本身结果的最大连续数组的值 >如果dp[i-1]<0,那么说明dp[i-1]对dp[i]没有任何贡献 >如果dp[i-1]>0,那么dp[i]的值就为dp[i-1]+num[i]
Python解法：
class Solution: def maxSubArray(self, nums: List[int]) -> int: res=nums[0] for i in range(1,len(nums)): nums[i]+=max(nums[i-1],0) res=max(res,nums[i]) return res
Java解法：
class Solution { public int maxSubArray(int[] nums) { int res=nums[0]; for(int i=1;i<nums.length;i++){ nums[i]+=Math.max(nums[i-1],0); res=Math.max(res,nums[i]); } return res; } }
