算法一：穷举式地尝试所有的可能 int maxSubsequenceSum(const int a[], int n) { int i, j, k; int thisSum, maxSum = 0; for (i = 0; i < n; i++) for (j = i; j < n; j++) { thisSum = 0; for (k = i; k < j; k++) thisSum += a[k]; if (thisSum > maxSum) maxSum = thisSum; } return maxSum; }
算法复杂度为O(n^3)（三重for循环）
算法二：算法一的改进 int maxSubsequenceSum(const int a[], int n) { int i, j; int thisSum, maxSum = 0; for (i = 0; i < n; i++) { thisSum = 0; for (j = i; j < n; j++) { thisSum += a[j]; if (thisSum > maxSum) maxSum = thisSum; } } return maxSum; }该算法去除了算法一中不必要的计算，时间复杂度为O(n^2)（两重for循环）。
算法三：分治（divide-and-conquer）策略 分治策略：分：把问题分成若干个（通常是两个）规模相当的子问题，然后递归地对它们求解。
治：将若干个问题的解4合并到一起并可能再做少量的附加工作，最后得到整个问题的解。
在这个问题中，最大子序列和可能在三处出现：即左半部序列、右半部序列、穿过中部从而占据左右两半部分的序列。前两种情况可以通过递归求解。而递归的基准情况（base cases）是序列只有一个元素（left == right），若该元素大于0，则返回该元素，否则返回0。第三种情况的最大和可以通过分别求出左边部分（包含左半部分最后一个）的最大和以及右边部分（包含右边部分的第一个）的最大和，再将它们相加得到。
int maxSubsequenceSum(const int a[], int left, int right) { int i, mid, maxLeftSum, maxRightSum; int maxLeftBorderSum, leftBorderSum; int maxRightBorderSum, rightBorderSum; if (left == right) { /*基准情况*/ if (a[left] >= 0) return a[left]; else return 0; } mid = left + (right - left) / 2; maxLeftSum = maxSubsequenceSum(a, left, mid); /*左半部分的最大和*/ maxRightSum = maxSubsequenceSum(a, mid+1, right); /*右半部分的最大和*/ /*下面求穿过中点的最大和*/ maxLeftBorderSum = 0, leftBorderSum = 0; for (i = mid; i >= left; i--) /*中点及其以左的最大和*/ { leftBorderSum += a[i]; if (leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum; } maxRightBorderSum = 0, rightBorderSum = 0; for (i = mid+1; i <= right; i++) /*中点以右的最大和*/ { rightBorderSum += a[i]; if (rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum; } /*返回三部分中的最大值*/ return max3(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum); } int max3(int a, int b, int c) { int maxNum = a; if (b > maxNum) maxNum = b; if (c > maxNum) maxNum = c; return maxNum; }以序列2，4，-1，-5，4，-1为例，其左半部分最大和为2 + 4 = 6；右半部分最大和为4，穿过中心的最大和为（-1 + 4 + 2）+ （-5 + 4）= 0。故该序列的最大子序列和为max（6，4，0）= 6。
时间复杂度分析: 假设T(n)为求解大小为n的最大子序列和问题所花费的时间。当n = 1是，T(1) = O(1)；当n > 1时，两次递归花费的总时间为2T(n/2),两个并列的for循环花费的时间是O(len(left)+len(right)) = O(n)，一共为2T(n/2)+O(n)。综上可列如下方程组：
T(1) = 1
T(n) = 2T(n/2) + O(n)
事实上，上述方程组常常通用于分治算法，由方程组可算出T(n) = O(nlogn)。
算法三利用递归较好的解决了最大子序列和问题，但仔细分析，在递归过程中，同一个元素很可能多次被操作，有没有更高效的算法？先上代码！
int maxSubsequenceSum(const int a[], int n) { int i; int maxSum, thisSum; maxSum = thisSum = 0; for (i = 0; i < n; i++) { thisSum += a[i]; if (thisSum > maxSum) maxSum = thisSum; else if (thisSum < 0) thisSum = 0; } return maxSum; }