题目：
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
分析：
实际上就是求最大的连续子序列和。
我们维护一个临时序列和，遍历数组，计算临时序列和，如果临时序列和大于最大值，就更新最大值，当临时序列和小于0时，也就证明此时的序列没有增长的空间了，将临时序列和更新为0，重新计算后续的序列和，最后返回最大值即可。
也可以使用分治法来求此题。对于一个数组来讲，最大的连续子序列和，要么在中间元素的左边，要么在中间元素的右边，要么跨过中间元素，根据这点可以利用分治来求。而跨过中间元素的最大子序列和，它的结果一点是从中间元素向两侧来计算的，我们可以从中间元素开始，分别向两端求解最大的序列和，最后返回两个子序列和的和，注意中间元素只计算一次。
程序：
C++
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.size() == )
return ;
return helper(array, , array.size()-);
}
int helper(vector<int>& nums, int left, int right){
if(left == right)
return nums[left];
int mid = (left + right) / ;
int maxResult = max(helper(nums, left, mid), helper(nums, mid+, right));
maxResult = max(maxResult, maxCrossMid(nums, mid, left, right));
return maxResult;
}
int maxCrossMid(vector<int>& nums, int mid, int left, int right){
int lsum = INT_MIN;
int tempSum = ;
for(int i = mid; i >= left; --i){
tempSum += nums[i];
lsum = max(tempSum, lsum);
}
tempSum = ;
int rsum = INT_MIN;
for(int i = mid+; i <= right; ++i){
tempSum += nums[i];
rsum = max(tempSum, rsum);
}
return (lsum + rsum);
}
};
Java
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length == 0)
return 0;
int max = array[0];
int tempSum = 0;
for(int num:array){
tempSum += num;
if(max < tempSum)
max = tempSum;
if(tempSum < 0)
tempSum = 0;
}
return max;
}
}