动态规划 [-2,1,-3,4,-1,2,1,-5,4]
指针i从头开始向右扫，dp[i]表示包含指针位置上的数的连续子数组的最大解
最大解dp[n]和dp[n-1]的关系：max(nums[n]，nums[n]+dp[n-1])
那么对应的结果： nums [-2,1,-3,4,-1,2,1,-5,4] dp=[-2,1,-2,4,3,5,6,1,5]; 由此可见 6为结果
class Solution { public int maxSubArray(int[] nums) { if (nums.length==0) {return 0;} else if (nums.length==1) return nums[0]; else { int[] dp= new int[nums.length]; dp[0]=nums[0]; for(int i=1;i<nums.length;i++){ dp[i]=Math.max(dp[i-1]+nums[i],nums[i]); } Arrays.sort(dp); return dp[dp.length-1]; } } } class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums)==0 : return 0 elif len(nums)==1: return nums[0] else : for i in range(1,len(nums)): nums[i]=max(nums[i],nums[i-1]+nums[i]) return max(nums)