c++ - 最大子数组问题

问题描述

问 题

牛客上的题目，求最大子数组，不知道哪里有问题。

#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);
} 

以上，希望能解决你的问题。

这篇关于c++ - 最大子数组问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！