问题描述：
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.
问题分析：
求解最大连续子数组和可采用分治法求解或者用动态规划（贪心）
分治法策略（二分）：
1.将一个数组分为三个部分：left，mid，right；
2.求解问题的答案会出现在left部分或者right部分或者mid和left、right的组合部分；
3.分别求出三个部分的最大值进行比较即可，依次递归
下面是分治法代码：
class Solution { public: int maxSubArray(vector<int>& nums) { return maxRes(nums,0,nums.size() - 1); } int maxRes(vector<int>& nums,int l,int h) { if(l >= h) return nums[l]; int mid = (l + h) / 2; int left = maxRes(nums,l,mid - 1); int right = maxRes(nums,mid + 1,h); int sum = 0; int ls = INT_MIN; for(int i = mid - 1;i >= l; i--) { sum += nums[i]; ls = max(sum,ls); } if(ls == INT_MIN) ls = 0; sum = 0; int rs = INT_MIN; for(int i = mid + 1;i <= h; i++) { sum += nums[i]; rs = max(sum,rs); } if(rs == INT_MIN) rs = 0; sum = max(max(ls + nums[mid],nums[mid]),max(nums[mid] + rs,nums[mid] + rs + ls)); return max(max(left,right),sum); } };贪心如下：
class Solution { public: int maxSubArray(vector<int>& A, int n) { int sum = 0, min = 0, res = A[0]; for(int i = 0; i < n; i++) { sum += A[i]; if(sum - min > res) res = sum - min; if(sum < min) min = sum; } return res; } };动态规划如下：
public int maxSubArray(vector<int>& A) { int n = A.length; int[] dp = new int[n];//dp[i] 代表以 A[i]结尾的子数组最大和; dp[0] = A[0]; int max = dp[0]; for(int i = 1; i < n; i++){ dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0); max = Math.max(max, dp[i]); } return max; }好了，有不懂的欢迎交流哈~~~
