数组最大连市续子序列和
数组最大连续子序列和
编程之美上的一个题：给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。对于S的所有非空连续子序列T，求最大的序列和。
思路
* 数组第一个元素A[0]和最大子数组和（a[i],...a[j])关系
* 1.当0=i=j时，a[0]就是最大子数组
* 2.当0=i<j时，最大子数组以a[0]开始
* 3.当0<i时，最大子数组跟a[0]没关系
编程之美上的一个题：给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。对于S的所有非空连续子序列T，求最大的序列和。
思路
* 数组第一个元素A[0]和最大子数组和（a[i],...a[j])关系
* 1.当0=i=j时，a[0]就是最大子数组
* 2.当0=i<j时，最大子数组以a[0]开始
* 3.当0<i时，最大子数组跟a[0]没关系
public static int getMax(int[] a) {
int l = a.length;
int start, all;
start = all = a[l-1];
for(int n = l-2; n >= 0; n--) {
start = Math.max(a[n], start + a[n]);
all = Math.max(all, start);
}
return all;
}