Max Sum

                                                                                  Total Submission(s): 142669    Accepted Submission(s): 33200

求出一个序列的所有的子集中元素的和中的最大值

简单dp

# include <stdio.h>
# define LEN 100010

int main(void)
{
    int i,T,n,j,sum,max,left,right,temp;
    int a[LEN];

    scanf("%d",&T);
    for(i=1; i<=T; ++i)
    {
        scanf("%d",&n);
        max = -1001;
        for(j=temp=0,sum=0; j<n; j++)
        {
            scanf("%d",&a[j]);
            sum += a[j];
            if(sum > max)
            {
                max = sum;
                left = temp;
                right = j;
            }
            if(sum < 0) 
            {
                sum = 0;
                temp = j+1;
            }
        }

        printf("Case %d:\n",i);
        printf("%d %d %d\n",max,left+1,right+1);
        if(i != T)
            printf("\n");
    }

    return 0;
}