杭电-1003 Max Sum

我的思路

子序列，相比原序列 少了一个头和尾，当然也有可能只是少了其中之一或者就等于原序列。

我们假设有一根指针在序列中游走，将指针前的元素称之为头元素，将指针后的元素称之为 尾元素，并设置一个max存储 指针前元素的最大值

什么情况下少 头？
当头元素的和小于0时，对于 我们求 Max Sum来说，小于0的头元素会导致Max Sum变小，故可以直接舍去。

 if(sum < 0){
     sum = 0;
     sum_begin = sum_end = j+1;
  }

什么情况下少 尾？
知道了max和它的始末位置，我们就完成了题目，所以当所取的数使得max最大时 少尾
但在我们的指针到达之前，永远也不知道下一个值是什么，它毫无疑问会对结果造成影响，故我们无法忽略它，我们中途无法确定要从哪里开始舍尾巴，所以必须遍历到最后一个值。

注意

第一个数为负数的情况
样例中第二行的第一个数5只是序列长度，而不是序列中的值，注意审题，避免发生不必要的疑惑。

AC 代码

#include<stdio.h>
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            int num = 0;
            scanf("%d",&num);

            int sum = 0;
            int sum_begin = 1;
            int sum_end = 1;

            int max = -1001; 
            int max_begin = 1;
            int max_end = 1;
            int number;

            for(int j=1;j<=num;j++){
                scanf("%d",&number);
                sum = sum + number;

                if(sum > max){//更新Max的值
                    max = sum;
                    max_begin = sum_begin;
                    max_end = j;
                }
                
                if(sum < 0){
                    sum = 0;
                    sum_begin = sum_end = j+1;//sum从负数之后的数重新开始计算
                }
            }
            //输出
            printf("Case %d:\n",i+1);
            printf("%d %d %d\n",max,max_begin,max_end);
            if(i != n-1)
                printf("\n");
        }
    }
    return 0;
}