0 引言
题目：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,
常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,
并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。
给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
1 举例/测试用例设置
（1）全是非负数的情况：
{9，3，6，8，0，1，2，4}
全部相加即可得到最大和，也就是说全体序列就是最大和序列
（2）全是非正数的情况：
{-1，-13，-9，-2，-7，0，-4}
某个最小的数即为最大连续子序列
（3）既有正数又有负数以及0的情况 ：
{9，3，-1，-13，6，8，0，-9，-2，-7，1，2，4}
1）将序列划分为不同的子序列，划分的依据是符号是否改变（从 “+ /0” 变为 “-” 或者 从“-/0”变为 “+” ），转化为
{12，-14，14，-18，7}
2）把满足从0或者正数开始，从0或者正数结束的所有序列全部列举出来，最后找到一个最大的序列，就是要求的结果序列。
1. 12，sum = 12
2. 12-》-14-》14，sum = 12
3. 12-》-14-》14-》-18-》7，sum = 1
4. 14 ，sum = 14
5. 14-》-18-》7， sum = 3
6. 7 ， sum = 7
7. 通过比较，得出最大连续子序列的和为14
2 具体例子抽象分析
通过1中的分析，可是算法应当分为以下两步进行
（1）对整个序列进行局部融合，利用额外的空间把融合序列存储起来 vector<int> myArray ，得到的序列具有以下特点：
1. 不包含0;
2. 奇偶相间;
（2）以开始和结束的值 >=0 为条件，计算所有的可能序列和
（3）如果所有的值均小于等于0，则返回整个序列中最大的数即可
3 demo
写了一版非常粗糙的代码，勉强调试通过了，明天再优化一下，先粘贴出来
int FindGreatestSumOfSubArray(vector<int> array) { // 判断序列是否为空 if(array.empty()) return 0; // 判断序列中是否存在正数，若不存在，则返回最小的数即可 int maxSum = array[0]; for(int i=1;i<array.size();i++){ if(array[i]>maxSum) maxSum = array[i]; } if(maxSum <= 0) return maxSum; // 若存在正数 // 1. 局部融合，将正数，负数和0分开融合，同时0不加入序列 vector<int> myArray; for(int i=0;i<array.size();){ int sum = 0; int flag; if(array[i] == 0) flag = 0; else flag = 1; int j = i; for(;j<array.size();j++){ // 子序列的首个数字为0，遍历但是不加入队列 if(flag == 0){ if(array[j] == 0) continue; else{ i = j; break; } } else{ if(array[j]*array[i] >= 0) sum += array[j]; if(array[j]*array[i]<0){ i = j; myArray.push_back(sum); break; } } } if(j == array.size()){ i = array.size(); myArray.push_back(sum); } } // 2. 遍历求解最大连续子序列的和 // 初始化maxSum int begin; for(int i=0;i<myArray.size();i++){ if(myArray[i]>0){ begin = i; maxSum = myArray[i]; break; } } for(int i=begin;i<myArray.size(); i += 2){ int subBegin = i; for(int j = subBegin + 2;j<myArray.size();j += 2){ int currentSum = myArray[subBegin]; for(int k = subBegin + 1;k<= j;k++) currentSum += myArray[k]; if(currentSum > maxSum) maxSum = currentSum; } } return maxSum; }
4 优化
代码毫无疑问有很多需要改进的地方，本身思路就不是很清晰，何况写代码的能力也不太行，结构很乱，看着着实费劲。。。参考了网友的代码以及《剑指offer》，对
算法作出如下调整。
（1）不对序列进行融合，转而采取一次遍历的方法，将算法的复杂度从O((n/2)^2)降到O(n);
（2）一次遍历的重点在于两个变量：当前子序列最小和 currentSum以及maxSum。当currentSum <= 0时，抛弃当前currentSum，原因在于该当前和与访问数相加得到的
和值一定小于访问数。此时，应当将访问数的值赋值给currentSum，从该数开始重新寻找最大和。
（3）当currentSum > maxSum时，更新该值.
demo如下：
int FindGreatestSumOfSubArray(vector<int> array){ if(array.empty()) return 0; int currentSum = array[0]; int maxSum = array[0]; for(int i=1;i<array.size();i++){ if(currentSum <= 0) currentSum = array[i]; else currentSum += array[i]; if(currentSum > maxSum) maxSum = currentSum; } return maxSum; }
对思路进行调整之后，写完整段代码只用了可能十来分钟，相比于上个思路用了大概一个半小时，这次可真是快太多了。。。所以说写代码思路才是决定性的。