HDU1003：Max Sum（简单dp）

题目： http://acm.hdu.edu.cn/showproblem.php?pid=1003

题意一目了然就不说了，算法是从左往右扫，一个暂时保存结果的值，如果区间结果<0,那么就更改左右区间的值，如果当前计算的值>暂存的最大值，则更改最大值，与其说这题是dp，不如说就是贪心。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define eps 1e-9
using namespace std;
int a[100010];
int main()
{
    int T,n,nowmax,premax,s,x,y;
    scanf("%d",&T);
    for(int z=1;z<=T;z++)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        premax=-1000;
        nowmax=0;
        x=1;
        y=1;
        for(int i=1;i<=n;i++)
        {
            nowmax+=a[i];
            if(nowmax>premax)
            {
                s=x;
                y=i;
                premax=nowmax;
            }
            if(nowmax<0)
            {
                x=i+1;
                nowmax=0;
            }
        }
        printf("Case %d:
",z);
        printf("%d %d %d
", premax,s,y);
        if(z!=T) cout<<endl;

    }
    return 0;
}