博客

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

给定一段长度为N的整数序列A，请从中选出一段连续的子序列（可以为0）使得这段的总和最大。

输入格式

第一行一个整数N表示序列的长度

第二行N个整数Ai表示序列的第i个元素

输出格式

一个整数表示选出的最大的和

样例输入

4

3 -10 1 1

样例输出

3

数据规模和约定

N<=100000,|Ai|<=100000

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    long max = 0,sum = 0,x;
    cin>>n;
    for (int i = 0; i < n;i++)
    {    
        scanf("%d", &x);
        if(sum+x>0)//只要没加成负数就有可能逆转大局
            sum += x;
        else//前面n个数加成负数了，后面的数不加前面的数会更大,这里重置一下sum
            sum = 0;
        max = max > sum ? max : sum;//记录最大值
    }
    cout << max << endl;
    system("pause");
    return 0;
}