问题描述：
给定一整数序列A1， A2，... ，An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大。
解决办法：
分治法：最大子序列和可能出现在三个地方：整个出现在输入数据的左半部分，整个出现在输入数据的右半部分，或者跨越输入数据的中部从而占据左右两个半部分。
1 double max3(double a, double b, double c){ 2 int d; 3 d = (a > b) ? a : b; 4 return (d > c) ? d : c; 5 } 6 7 int MaxSubSum(const int A[], int left, int right){ 8 int center = 0; 9 int maxleftsum = 0, maxrightsum = 0; 10 int leftbordersum = 0, rightbordersum = 0; 11 int maxleftbordersum = 0, maxrightbordersum = 0; 12 13 if(left == right) 14 if(A[left] > 0) 15 return A[left]; 16 else 17 return 0; 18 else 19 ; 20 21 center = (left + right) / 2; 22 maxleftsum = MaxSubSum(A, left, center); 23 maxrightsum = MaxSubSum(A, center + 1, right); 24 25 for(int i = center; i >= left; i--){ 26 leftbordersum += A[i]; 27 if(leftbordersum > maxleftbordersum) 28 maxleftbordersum = leftbordersum; 29 } 30 31 for(int i = center + 1; i <= right; i++){ 32 rightbordersum += A[i]; 33 if(rightbordersum > maxrightbordersum) 34 maxrightbordersum = rightbordersum; 35 } 36 37 return max3(maxleftsum, maxrightsum, maxleftbordersum + maxrightbordersum); 38 } 39 40 int MaxSubsequenceSum(const int A[], int N){ 41 return MaxSubSum(A, 0, N - 1); 42 }
动态规划：
原文：https://www.cnblogs.com/longlively/p/9053110.html