[恢]hdu 1003

2011-12-20 08:35:28

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1003

题意：找n个数里连续的一串和最大。

mark：dp。wa了2次。第一次没考虑负数。第二次少考虑-1 2这种情况。

代码：

# include <stdio.h>


int n, a[100010] ;
int spos, epos, max_ans ;


int gao()
{
    int i, s = 0, ans = a[0] ;
    spos = epos = 0 ;
    max_ans = a[0] ;
    for (i = 1 ; i < n ; i++)
    {
        if ((ans + a[i]) < 0 || (ans<0 && a[i] >= 0))
            ans = a[s = i] ;
        else
            ans += a[i] ;
        if (ans > max_ans)
        {
            max_ans = ans ;
            spos = s ;
            epos = i ;
        }
    }
}


int main ()
{
    int T, i , nCase = 1 ;
    scanf ("%d", &T) ;
    while (T--)
    {
        scanf ("%d", &n) ;
        for (i = 0 ; i < n ; i++)
            scanf ("%d", &a[i]) ;
        gao() ;
        if (nCase != 1) printf ("\n") ;
        printf ("Case %d:\n", nCase++) ;
        printf ("%d %d %d\n", max_ans, spos+1, epos+1) ;
    }
    return 0 ;
}