牛客上的题目,求最大子数组,不知道哪里有问题。
#include <iostream>#include <vector>using namespace std;int main(){ int n; cin >> n; if(n < 1 || n > 100000) return false; vector<int> vec(n); int temp; while(cin >> temp) vec.push_back(temp); if(n == 1){ cout << vec[0]; return 0; } int maxSum = vec[0]; int curSum = vec[0]; for(int i = 1; i < vec.size(); i++){ if(curSum < 0) curSum = vec[i]; else{ curSum += vec[i]; } if(curSum > maxSum) maxSum = curSum; } cout << maxSum <<endl; return 0;}
解决方案
楼主你的算法没有问题,楼上都没抓住重点,你只是在vector初始化的时候出了问题。
vector<int> vec(n); int temp; while(cin >> temp) vec.push_back(temp);
这里错了,楼主,你用的vector<int>vec(n);这句话已经已经将vec声明为含有n个0的数组,你后面又执行vec.push_back(temp);因此最后你的vec一共有2n个元素。
如果vec中有正数的话,不会影响你的结果,所以你对了90%的样例。但是如果全是负数的话,最大连续和将恒为0,而不是你想要的结果。
eg:[0,0,0,-1,2,1]、[0,0,0,-1,-2,-3];
应该采用这种方式构造:
vector<int> vec(n);int temp;for(auto &val:vec){ cin>>val;}或者vector<int> vec;int temp;while(n--){ cin>>temp; vec.push_back(temp);}
以上,希望能解决你的问题。