hdu1003 参考答案

!cplusplus
//533278 2008-03-30 19:03:17 Accepted 1003 31MS 264K 1206 B C++ whiteTiger 非DP方法 
#include <stdio.h>

int main(){
    int CaseNum;
    scanf("%d", &CaseNum);
    int a[100000];
    for(int Case = 0; Case < CaseNum; Case++){
        int num;             
        scanf("%d",&num);
        for(int i = 0; i < num; i++){
            scanf("%d", &a[i]);
        }
        int currentSum, maxSum, start, end;
        //最大子段和
        start = 0;
        end = 0;
        maxSum = -1001;     //记录最大值，n范围-1000-1000
        currentSum = 0;     //记录当前总和
        for(int i= 0; i < num; i++){
            for(int j = i; j  < num; j++){
                currentSum += a[j];
                if(currentSum > maxSum){
                    maxSum = currentSum;
                    start = i+1;
                    end = j+1;
                }
                if(currentSum < 0){
                    i = j;
                    currentSum = 0;
                    break;
                }               
            }
            currentSum = 0;
        }
        printf("Case %d:\n", Case+1);
        printf("%d %d %d\n", maxSum, start, end);
        if(Case != CaseNum -1){
            printf("\n");
        }
    }
    return 0;
}