看到这道题，我首先想的是用滑动窗口去解，但是一时间想不出让窗口滑动的条件，于是就暴力解答了，没想到竟然过了～
时间复杂度O(n^2) 连O(n)的复杂度都没有达到，更别说用分治法了。。。
暴力解法代码
class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();int MaxSum = nums[0];for(int i = 0 ; i < n ; i ++){int temp = 0;for(int j = i; j < n ; j ++ ){temp += nums[j];MaxSum = MaxSum > temp ? MaxSum : temp;}}return MaxSum;}
};
当然光过题是不行的，一定要追求一下最优解
于是在网上搜集了一下，看到了用 Kadane's algorithm来求解子数组最大和问题
该算法这里讲解的很好，可以去康康
即在数组[-2,1,-3,4,-1,2,1,-5,4]当我们想计算-1这个元素为终点的子数组的最大和的时候，我们可以分为两种情况讨论：
一种是包括前面的元素，就是需要知道-1前一个元素4为终点的子数组的最大和，这样只要把以4为终点的子数组的最大和，加上-1就可以了；
另一种情况是不包括前面的元素，因为以4为终点的子数组的最大和可能是一个负数，-1不如抛掉他们，自己自立门户，即只有-1一个元素。
那么我们就可以得到这个问题的转移方程：
localMax = Math.max(nums[i], localMax + nums[i]);
其中localMax是以当前元素结尾的子数组的最大和。
当然，接下来，我们要和全局最大值进行比较，如果比全局最大值还要大，就更新全局最大值：
max = Math.max(max, localMax);
利用经典的动态规划算法Kadane's algorithm
我的代码如下
class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();int MaxSum = nums[0]; int LocalMaxSum = nums[0];for(int i = 1 ; i < n ; i ++){LocalMaxSum = nums[i] > ( LocalMaxSum + nums[i] ) ?nums[i] : ( LocalMaxSum + nums[i] );MaxSum = MaxSum > LocalMaxSum ?MaxSum : LocalMaxSum;}return MaxSum;}
};