||_ 题目描述
||_ 分析 本题的核心是计算出一个序列的所有子序列中元素和为最大时的值，不要求输出对应的子序列是什么，而只要求输出和的最大值是多少。
法一： 我们把序列分成两半（左边和右边），那么和最大的序列要么出现在左边序列，要么出现在右边序列，要么横跨左右两边。而左边序列又可以分成两半，以此类推；右边序列也一样。由此，便可分而治之了。
下面是代码：
int maxSubArray(int* nums, int numsSize) { return findMax(nums,0,numsSize-1); } int findMax(int* nums,int left,int right){ if(left==right) return nums[left]; int mid=left+(right-left)/2; int lmax=findMax(nums,left,mid); int rmax=findMax(nums,mid+1,right); int lpart=nums[mid]; int rpart=0; int temp=0; for(int i=mid;i>=left;i--){ temp+=nums[i]; if(temp>lpart) lpart=temp; } temp=0; for(int i=mid+1;i<=right;i++){ temp+=nums[i]; if(temp>rpart) rpart=temp; } return lmax>rmax?lmax>(lpart+rpart)?lmax:(lpart+rpart):rmax>(lpart+rpart)?rmax:(lpart+rpart); }那复杂度怎么样呢？ T(n)=2T(n/2)+O(n); 由Master Theorem可得，计算的复杂度为O(nlogn)
法二： 我们要明白三点， ``I、最大子序列的开始可以是数组中的任意一个元素。所以我们可以通过一次遍历就肯定经过过最大子序列的开始位置。 ``II、最大子序列的结尾是什么位置呢？我们可以不管，因为我们只需要输出值就好。只要用一个temp变量一直保存所有已遍历情况中的最大值就好。 ``III、简化计算的核心：我们并不需要遍历所有完子序列，如（-2，1，2，-4，5）和（1，2，-4，5）序列，因为-2+1<1,后者的结果总会比前者的大，那么我们便可直接排除前者，而只遍历后者了。
可能说得有点绕，直接看代码吧：
int maxSubArray(int* nums, int numsSize) { int i=0; int suma=nums[0]; int sumb=0; int max=nums[0]; for(i=1;i<numsSize;i++){ sumb += nums[i]; suma += nums[i]; if(suma>max) max=suma; if(sumb>max) max=sumb; if(suma<=sumb) suma=0; else sumb=0; } return max; }那复杂度怎么样呢？ 我们可以很直观得看到，只有一个for循环，所以复杂度为O(n)
