USACO2011 Jan:公司利润

简要题意：

　　奶牛开了家公司，已经连续运作了N 天。它们在第i 天获得了Ai元的利润，不过有些天是亏钱的，这种情况下利润就是一个负数。约翰想为它们写个新闻，吹嘘它们的惊人业绩。请你帮助他选出一段连续的日子，长度不限，但至少要包括一天，使得公司在这段日子里的利润之和最大。

输入格式：

　　• 第一行：单个整数N，1 ≤ N ≤ 10^5

　　• 第二行到第N + 1行：第i + 1行有一个整数Ai，−1000 ≤ Ai ≤ 1000

输出格式：

　　• 单个整数：表示最大的利润之和

样例输入：

7
-3
4
9
-2
-5
8
-3

样例输出：

样例解释：

　　选择第三天到第六天，4 + 9 − 2 − 5 + 8 = 14

题解：

　　这道题求的是最大连续子段和，很经典的题，也是贪心做法，一旦利润和为负数则立即停止往后加，以免影响后面的最大和

参考代码：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int a[];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    int sum=,ans=-;

    for(int i=;i<=n;i++)

    {

        if(sum<) sum=;

        sum+=a[i];

        if(ans<sum) ans=sum;

    }

    printf("%d\n",ans);

    return ;

}

巴特西