题目描述

---

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)

代码实现

---

//动态规划 class Solution { public: //状态转移方程： sum[i]=max(sum[i-1]+a[i],a[i]) int FindGreatestSumOfSubArray(vector<int> array) { if(array.empty()) return 0; int maxsum = array[0], tempsum = array[0]; //注意初始值 不能设为0 防止只有负数 for(int i = 1; i < array.size(); i++) //从1开始 因为0的情况在初始化时完成了 { //tempsum = (tempsum < 0) ? array[i] : tempsum + array[i]; if(tempsum<0){ tempsum=array[i]; } else{ tempsum=tempsum+array[i]; } //sum = (tempsum > sum) ? tempsum : sum; if(tempsum>maxsum){ maxsum=tempsum; } else{ maxsum=maxsum; } } return maxsum; } }; class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { vector<int> cent; int sum = 0; bool orZ = true; if (array.size() <= 0){ return 0; } for(int i = 0;i < array.size();i++) { if(array[i]< 0){ orZ = false; } sum += array[i]; cent.push_back(sum); } int k = 0; for(int j =0 ;j< cent.size();j++){ if(cent[j]> cent[k]){ k = j; } } if(orZ){ return cent[k]; } else{ return cent[k]+1; } } };