最大子数组问题

Question

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

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

Answer 1

• 楼主你的算法没有问题，楼上都没抓住重点，你只是在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);
} 

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

Answer 2

没细看代码，对 c++ 不熟悉，不过简单想一下，求解过程应该是逆序遍历吧。

好吧，不说过个，说它的测试用例。

很显示，当全为负数的情况下，最大和应该为 空列表 ，而一个空列表的成员的和，是不是为 0 ？ 我觉得可以是（当然，你硬要说空列表的和应该定义为“异常”，我也说服不了你）。

Answer 3

没有编译你的问题扫了一下这里有问题(不保证其他地方没问题):
这里curSum实际上名字起的有点歧义，你这已经是累加的和了，那么如果总和小于0，这一个区间对后面的数字就没多贡献了，应该把curSum状态复位为0，后面重新加起来.

    for(int i = 1; i < vec.size(); i++){
          // 这里curSum实际上名字起的有点歧义，你这已经是累加的和了，那么如果总和小于0，这一个区间对后面的数字就没多贡献了，应该把curSum状态复位为0，后面重新加起来.
          if(curSum < 0)
            curSum = vec[i];

贴下我的答案，参考下，另外建议刷题到leetcode吧，我看比牛客规范一些啊. 竟然用main的返回值当做测试项.

    int maxSubArray(vector<int>& nums) {
     if(nums.empty()) return 0;
 
     int size = nums.size();
     int maxNum = nums[0];
     int sumNum = nums[0];
     for(int i=1; i<size; ++i)
     {   
         if(sumNum < 0) sumNum = 0;
 
         sumNum += nums[i];
         if(maxNum < sumNum) maxNum = sumNum;
     }
     return maxNum;

Answer 4

你这个就是经典的最大子序列和算法 百度一下吧 很多的 算法书应该都有这个算法解析 最简单的是一个线性的算法我记得