给定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( < 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。

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

6
-2 11 -4 13 -5 -2
10
-10 1 2 3 4 -5 -23 3 7 -21
6
5 -8 3 2 5 0
1
10
3
-1 -5 -2
3
-1 0 -2
0

20 11 13
10 1 4
10 3 5
10 10 10
0 -1 -2
0 0 0


Hint
Hint
 
Huge input, scanf is recommended.

浙大计算机研究生复试上机考试-2005年

JGShining   |   We have carefully selected several similar problems for you:  1003 1087 1176 1203 1257 

毫无疑问，一般求最大公共子序列的题目，考得都是动态规划,也就是DP.

本题，虽然不像01背包这么简单，但是我选择的思路也是非常简单易懂.(看到的解析中最简单的思路......)

import java.io.*;
import java.util.*;

public class Main
{

	public static void main(String[] args)
	{
		Scanner input = new Scanner(System.in);
		while(input.hasNext())
		{
			int n=input.nextInt();
			if(n==0) break;
			int a[] = new int[n];            //开一个数组用来存储给定序列
			for(int i=0;i<n;i++)
			{
				a[i]=input.nextInt();
			}
			int sum,max,start,end,cnt=0;    //sum存当前和，max存当前最大和,start为起始元素点，end为结束元素点
			int temp=0;                     //用来临时存起始点，也就是下一个start，cnt记录负数个数.
			sum=start=end=0;
			max=a[0];
			for(int i=0;i<n;i++)
			{
				sum+=a[i];                  
				if(sum>max)                 //如果sum比最大值大，i为最后标记点end,最大值为sum.
				{
					end=i;
					max=sum;
					start=temp;
				}                           
				else if(sum<0)				//如果当前sum<0并且sum<=max，即当前sum肯定不是最大值
				{
					temp=i+1;               //起始位置应为下一个数的下标
					sum=0;
					cnt++;                  //记录负数个数
				}
			}
			if(cnt==n)                      //cnt==n则所有的数为负数
			{
				System.out.println("0"+" "+a[0]+" "+a[n-1]);
			}
			else 
			{
				System.out.println(max+" "+a[start]+" "+a[end]);
			}
		}
	}

}