原题链接：

题目描述：

    给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。

输入：

    测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( K< 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。

输出：

    对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。

样例输入：

6-2 11 -4 13 -5 -210-10 1 2 3 4 -5 -23 3 7 -2165 -8 3 2 5 01103-1 -5 -23-1 0 -20

样例输出：

20 11 1310 1 410 3 510 10 100 -1 -20 0 0

题解：

　　

经典的一道题。直接上代码：

1 #include 
      
        2 #include 
       
         3   4 int arr[10001]; 5 typedef struct Result{ 6         int max; 7         int begin; 8         int end; 9 }Result;10  11 bool isNeg(int a[],int size){12      for(int i=0; i
        
         =0)14                     return false;        15      }   16      return true;17 }18 void maxSubArray(int a[],int size,Result* res){19     int sum = 0;20     int max = 0;21     int cur = 0;22     int begin=0;23     int end=0;24     bool flag = false;25     int begin2 = a[0];26     int end2 = a[0];27     if(isNeg(a,size)){28         res->max = 0;29         res->begin = a[0];30         res->end = a[size-1];              31     }else{32         while(cur
         
          max){              35               max = sum;36               begin = begin2;37               end = a[cur-1];38          }else if(sum<0){39               sum = 0;40               begin2 = a[cur];//假定后面还会有更大的字串，记录下其实位置 41               end2 = a[cur];42          }              43         }44         res->max = max;45         res->begin = begin;46         res->end = end;  47     }48      49 }50 int main(){51     int K;52     //freopen("1011.in","r",stdin);53     //freopen("1011.out","w",stdout);54     Result* res = (Result*)malloc(sizeof(Result));55      56     while(scanf("%d",&K) && K!=0){57          for(int i=0; i
          
           max,res->begin,res->end);       62     }63     return 0;   64 }