问题描述： 给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
样例： 给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6
分析： 解决这个问题至少有4种方法
算法1 穷举法
我们穷举出所有的子数组，然后从这些子数组中找出最大的
int MaxSubseqSum1(int List[], int N){ int ThisSum, MaxSum = 0; int i,j,k; for (i = 0; i < N; i++)//i是子数组的左端 { for (j = i; j < N; j++)//j是子数组的右端 { ThisSum = 0;//ThisSum是List[i]到List[j]的子数组的和 for (k = i; k <= j; k++) ThisSum += List[k]; if(ThisSum > MaxSum)//如果刚得到的这个子数组和更大 MaxSum = ThisSum;//则更新结果 } } return MaxSum;}时间复杂度：O(N3)
算法2 优化的穷举法
第一个算法中，最里面的循环，对于固定的i，当j增大了1，k循环需要从新从i加到j。事实上，第j部就加上List[j]即可。
int MaxSubseqSum2(int List[], int N){ int ThisSum, MaxSum = 0; int i,j; for (i = 0; i < N; i++) { ThisSum = 0; for (j = i; j < N; j++) { ThisSum += List[j]; // 对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可 if(ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum;}时间复杂度：O(N2)
算法3：分而治之
步骤： 1. 将序列分为左右两个子数组 2. 递归地求两个子数组的最大和S左和S右 3. 从中间的点分别找出左右，跨过分界线的最大子数组的和S中 4. Smax=maxS左,S右,S中
/*算法3：分而治之*/inx Max3(int A, int B, int C){ return A > B ? A > C ? A : C : B > C ? B : C;}int DivideAndConquer(int List[], int left, int right){ int MaxLeftSum, MaxRightSum; int MaxLeftBorderSum, MaxRightBorderSum; int LeftBorderSum, RightBorderSum; int center,i; if(left == right) //递归终止条件，子数组只有一个数字 if(List[left] > 0) return List[left]; else return 0; //分的过程 center = (left+right)/2; MaxLeftSum = DivideAndConquer(List,left,center) MaxRightSum = DivideAndConquer(List,center+1,right) //跨界求最大子数组和 MaxLeftBorderSum = 0; LeftBorderSum = 0; for (i = center; i >= left; i--) { LeftBorderSum += List[i]; if(LeftBorderSum > MaxLeftBorderSum) MaxLeftBorderSum = LeftBorderSum; }//左边扫描结束 MaxRightBorderSum = 0; RightBorderSum = 0; for (i = center+1; i < right; i++) { RightBorderSum += List[]; if(RightBorderSum > MaxRightBorderSum) MaxRightBorderSum = RightBorderSum; }//右边扫描结束 //治的过程 return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);}int MaxSubseqSum3(int List[], int N){ return DivideAndConquer(List, 0, N-1);}算法4：在线处理（动态规划）
核心思想：一旦发现子数组的和为负数，弃置，重新一个新数组。
int MaxSubseqSum4(int List[], int N){ int ThisSum, MaxSum; int int; ThisSum = MaxSum = 0; for (i = 0; i < N; i++) { ThisSum += List[i]; if(ThisSum > MaxSum) MaxSum = ThisSum; else if(ThisSum < 0) ThisSum = 0; } return MaxSum;}python
#动态规划def MaxSubseqSum(A): max_ending_here = max_so_far = A[0] for x in A[1:]: max_ending_here = max(x, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far
