九度OJ 题目：最大子向量和

时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：396
解决：109
 
题目描述：
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天JOBDU测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？
 
 
输入：
输入有多组数据,每组测试数据包括两行。
 
第一行为一个整数n(0<=n<=100000),当n=0时,输入结束。接下去的一行包含n个整数(我们保证所有整数属于[-1000,1000])。
 
 
 
 
 
输出：
对应每个测试案例,需要输出3个整数单独一行,分别表示连续子向量的最大和、该子向量的第一个元素的下标和最后一个元素的下标。若是存在多个子向量,则输出起始元素最小的那个。
 
 
样例输入：
3
-1 -3 -2
5
-8 3 2 0 5
8
6 -3 -2 7 -15 1 2 2
0
样例输出：
-1 0 0
10 1 4
8 0 3[cpp]  
/********************************* *   
日期：2013-2-18 *  
 
 作者：SJF0115 *   
题号: 九度OJ 题目15：最大子向量和 *   
 
  结果：AC *   
来源：剑指
Offer：名企面试官精讲典型编程题 *
   总结
**********************************/  
#include<stdio.h>     int Num[100001];    int main() {      int i,j,n,sum,Max,indexStart,indexEnd,currentStart;      while (scanf("%d",&n) != EOF && n != 0){          sum = 0;          for(i = 0;i < n;i++){              scanf("%d",&Num[i]);              //初始化               if(i == 0){                  Max = Num[i];                  currentStart = 0;                  indexStart = 0;                  indexEnd = 0;              }              //如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和               if(sum < 0){                  sum = Num[i];                  currentStart = i;              }              else{                  sum += Num[i];              }              if(sum > Max){                  Max = sum;                  indexStart = currentStart;                  indexEnd = i;              }              //注意：若是存在多个子向量,则输出起始元素最小的那个               else if(sum == Max){                  if(Num[indexStart] > Num[currentStart]){                      indexStart = currentStart;                      indexEnd = i;                  }              }          }          printf("%d %d %d\n",Max,indexStart,indexEnd);      }//while       return 0;

补充：软件开发 , C# ,