给定一个数组，当中有正负数，求当中的一段“子数组”（即任意长度，连续的数字），使得这个“子数组”的和是所有“子数组”和中最大的，
如给定的数组为12， -8， 5， 66， -21， 0 ，35， -44，7，则最大的和的子数组为{12， -8， 5， 66， -21， 0 ，35}，最大的和为89.
------解决方案--------------------
这就是个简单的典型的“动态规划”题目。
数组：x1,x2,x3,……xn
思路，首先是寻找最优子结构，这点要依靠一些经验规则。
这里的最优子结构就是
f(i)定义为以xi结尾的最大字串和。
那么f(i+1)就可以考虑
如果xi+1大于等于0或者f(i) + xi+1 > 0，那么f(i+1) = f(i) + xi+1；
如果f(i) + xi+1 <= 0,那么f(i+1) = 0；
递推公式就是有了。下面用DP的典型结构给出代码：
- Java code
public class MaxSubSequence { public static void main (String[] args) { int[] input = new int[]{3,73,-95,42,43,29,-30,-87,74,-53,22,74,-91,-1,-27,-8,-14,26,-67,-74}; int[] fDp = new int[input.length]; //f for dp //process first element if (input[0] > 0) fDp[0] = input[0]; for (int i = 1;i < input.length;++i){ if (fDp[i-1]+input[i] > 0) fDp[i] = fDp[i-1]+input[i]; else fDp[i] = 0; } //find the max value in fDp int maxSun = 0; for (int sum : fDp) if (sum > maxSun) maxSun = sum; System.out.println("max sum : " + maxSun); } }