条件：具有最优子结构；子解集合具有重复
最大子段和
【问题描述】
给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为
Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
例如，当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为20
【分析】
设数组a[k]，1<= k <= n，最大子段和X被定义为：
不妨设
那么这里的b[j]表示以第j个元素结尾的子段的和的最大值。这样的话，
根据b[j]的定义，b[j] = b[j-1] + a[j] b[j - 1] > 0
a[j] b[j - 1] >= 0
[1]变形1：求矩阵的最大子矩阵和
pku1050
http://www.cnblogs.com/blackcruiser/articles/1786888.html
求解思路：将二维的问题转化为一维的问题求解。
[2]变形2：求最大m子段和
************************************************
还没有看USACO的解题答案：
The Longest Prefix