动态规划例题：最大连续子序列和

问题：

给定一个数字序列a1, a2,..., an, 求i，j（1<=i<=j<=n），使得ai + ... + aj 最大，

输出这个最大和。

输入：6

          -2 11 -4 13 -5 -2

输出：20

解：

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		int[] dt = new int[n];// 保存各个点的最大连续子序列和
		// dt[i]表示以a[i]作为末尾的连续序列的最大和
		dt[0] = a[0];// 边界，a[0]就是在0点连续子序列和的最大值
		for (int i = 1; i < n; i++) {
			// 状态转移方程
			dt[i] = Math.max(dt[i - 1] + a[i], a[i]);
		}
		int num = 0;// 最大连续子序列和的结尾那个点的下标
		for (int i = 0; i < n; i++) {// 找出dt[]中值最大的那个点的下标
			if (dt[i] > dt[num]) {
				num = i;
			}
		}
		System.out.println(dt[num]);
	}
}