Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.
click to show more practice.
More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
问题：找出给定int数组如[-2,1,-3,4,-1,2,1,-5,4]的最大连续子串之和比如[4,-1,2,1]是6最大，而子串[-3，4,-1,2]是2
思想：动态规划。若求前i项子串中最大连续子串的和，可以理解成求前i-1个元素中最大元素和+第i个元素到来所引起的情况（i要么和前面i-1项组成一组，要么自己一组，看它本身和前i-1项子串和是正还是负）；而整个数组n各元素中的最大连续子串和就是从前1，2...i,i+1...n个最大连续子串和的最大值。
public int maxSubArray(int[] nums){ if(nums==null||nums.length<1) return 0; if(nums.length==1) return nums[0]; int max=nums[0]; int curMax=nums[0];//前i项元素中子串的最大值，初始是前1项时 for(int i=1;i<nums.length;i++){ curMax=Math.max(curMax+nums[i], nums[i]); max=Math.max(curMax,max);//n中情况下，前i项最大和中的最值 } return max; }
public int maxSubArray2(int[] nums){ if(nums==null||nums.length<1) return 0; if(nums.length==1) return nums[0]; int max=nums[0]; int[] maxArray=new int[nums.length]; maxArray[0]=nums[0]; for(int i=1;i<nums.length;i++){ if(maxArray[i-1]+nums[i]>nums[i]){ maxArray[i]=maxArray[i-1]+nums[i]; //max=Math.max(max, maxArray[i]); }else{ maxArray[i]=nums[i]; } max=Math.max(max, maxArray[i]); } return max; }
