2013
11-11

# Max Sequence

Give you N integers a1, a2 … aN (|ai| <=1000, 1 <= i <= N).

You should output S.

The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

For each test of the input, print a line containing S.

5
-5 9 -5 11 20
0


40

//* @author
import java.util.Scanner;
public class Main{
public static void main(String args[]){

int data[]=new int[100000];
int dp[]=new int[100000];
int n;
Scanner in=new Scanner(System.in);
while((n=in.nextInt())!=0){

int sum = 0, tmp = -999999999;
for(int i = 0; i < n; i++){
data[i]=in.nextInt();
sum += data[i];
if(sum > tmp)
tmp = sum;
dp[i] = tmp;
if(sum < 0)
sum = 0;
}
sum = 0;
int ans = -999999999;
for(int i = n-1; i > 0; i--){
sum += data[i];
if(dp[i-1]+sum > ans)
ans = dp[i-1]+sum;
if(sum < 0)
sum = 0;
}
System.out.printf("%d\n", ans);
}
}
}

1. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

2. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。