hdu~1003 (간단한 dp)

Max Sum
최대 필드의 합을 구합니다.
dp[i]로 저장된 것은 전 i개 수 중 선택한 연속수의 가장 좋은 해답(즉 최대)
dp[i]에서 가장 큰 수의 위치는 끝 위치입니다
끝에서 앞으로 옮겨다니며, 맨 앞의 비음수는 시작 위치이다
예를 들어 3-42-13에 대응하는 dp는 3-1214,
5 위치는 끝 위치, 2 위치는 시작 위치

#include <stdio.h>
#define MAX 100000

int dp[MAX+5],num[MAX+5];

int main()
{
    int t,ti;
    scanf("%d",&t);
    for(ti=1;ti<=t;ti++)
    {
        int n,i,j;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&num[i]);
        dp[1]=num[1];
        for(i=2;i<=n;i++)       //dp[i]      
            dp[i]=dp[i-1]>0?dp[i-1]+num[i]:num[i];  

        int start=1,end=1,max=dp[1];
        for(i=1;i<=n;i++)       //       ，       
        {
            if(max<dp[i])
            {
                max=dp[i];
                end=i;
            }
        }
        start=end;
        for(i=end;i>=1;i--) //         ，              
        {
            if(dp[i]>=0)
                start=i;
            else
                break;
        }
        printf("Case %d:
",ti);
        printf("%d %d %d
",max,start,end);
        if(ti!=t)
            printf("
");
    }
    return 0;
}