NYOJ--44（动态规划）-题目----------------------------- 子串和

/*子串和
 时间限制：5000 ms  |  内存限制：65535 KB
 描述
 给定一整型数列{a1,a2...,an}，找出连续非空子串{ax,ax+1,...,ay}，使得该子序列的和最大，其中，1<=x<=y<=n。
 输入
 第一行是一个整数N(N<=10)表示测试数据的组数）
 每组测试数据的第一行是一个整数n表示序列*有n个整数，
 随后的一行里有n个整数I(-100=<I<=100)，表示数列中的所有元素。(0<n<=1000000)
 输出
 对于每组测试数据输出和最大的连续子串的和。
 样例输入
 1
 5
 1 2 -1 3 -2
 样例输出
 5*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class nyoj44 {

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int T = Integer.parseInt(br.readLine());
while (T-- > 0) {

int n = Integer.parseInt(br.readLine());
int[] data = new int[n];
String in[] = br.readLine().split(" ");
for (int i = 0; i < data.length; i++)
data[i] = Integer.parseInt(in[i]);

int max = data[0];
for (int i = 1; i < data.length; i++) {
// 第i个数有两个选择，加与不加前面那个数
int temp = Math.max(data[i], data[i - 1] + data[i]);
// 更新data[i]和max
data[i] = temp;
max = temp > max ? temp : max;
}
System.out.println(max);
}
}
}