HDOJ链接 http://acm.hdu.edu.cn/showproblem.php?pid=1003 不了解题目的朋友可以先看一下题目，在这里就不再详细介绍了。（文章内容和解题思路不完全相同）
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence.
For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
下面就直接进行分析：
方法一：暴力破解，时间复杂度：O(n^3)
对所有情况的字串进行计算，然后求出和最大的子串。这个就不详细解释了看代码就能明白。
private void test01() { int maxValue = 0; for (int i = 0; i < array.length; i++) {// 第一次循环 for (int j = i; j < array.length; j++) {// 第二次循环 int thisMaxValue = 0; // 这里置零 for (int k = j; k < array.length; k++) {// 开始新的循环计算thisMaxValue thisMaxValue += array[k]; } if (thisMaxValue > maxValue) { maxValue = thisMaxValue; } } } System.out.println(maxValue); }
方法二：还是暴力破解，时间复杂度：O(n^2) 。需要注意的是和方法一的区别。
public void test02() { int maxValue = 0; for (int i = 0; i < array.length; i++) {// 第一次循环 int thisMaxValue = 0; for (int j = i; j < array.length; j++) {// 第二次循环 thisMaxValue += array[j]; // 这里没有置零，利用了上个thisMaxValue数值 if (thisMaxValue > maxValue) { maxValue = thisMaxValue; } } } System.out.println(maxValue); }
区别：方法一每次都是对子串全部循环一遍，而方法二，利用了第二层循环，不再对子串进行全部循环。
方法三：分治算法，递归求解。时间复杂度：O(nlogn)
public void test03() { System.out.println(start(array, 0, array.length / 2, array.length - 1)); } //递归方法 private int start(int[] array, int left, int mid, int right) { if (left == right) { return array[left]; } int leftMaxValue = start(array, left, (left + mid) / 2, mid);// 递归求左子串的最大值 int rightMaxValue = start(array, mid + 1, (mid + right) / 2, right);// 递归求右子串的最大值 /** 开始计算跨两边的最大子序列
toLeftMaxValue <—— MaxSum(mid to left)
toRightMaxValue<—— MaxSum(mid to right)
midMaxValue = toLeftMaxValue +toRightMaxValue; **/ int toLeftMaxValue = 0; int tempMaxValue = 0; for (int i = mid; i >= 0; i--) { tempMaxValue += array[i]; if (tempMaxValue > toLeftMaxValue) { toLeftMaxValue = tempMaxValue; } } tempMaxValue = 0; int toRightMaxValue = 0; for (int i = mid + 1; i <= right; i++) { tempMaxValue += array[i]; if (tempMaxValue > toRightMaxValue) { toRightMaxValue = tempMaxValue; } } //计算出跨左右两边的最大子串和 int midMaxValue = toRightMaxValue + toLeftMaxValue; //返回本层循环的最大子串和 return Math.max(Math.max(leftMaxValue, midMaxValue), rightMaxValue); }
需要好好考虑的是为何在计算夸两边最大子串和的时候需要 toRightMaxValue + toLeftMaxValue，考虑明白这个问题，方法三也就明白了。因为 toLeftMaxValue 的子串和 toRightMaxValue 的子串是连接着的，其节点就是mid,所以两者完全可以进行相加以求出跨两边的最大子串和。
方法四：遍历累积。时间复杂度：O(n)。
public void test04() { int maxValue = 0; int thisMaxValue = 0; for (int i = 0; i < array.length; i++) { thisMaxValue += array[i]; if (thisMaxValue > 0) { maxValue = thisMaxValue > maxValue ? thisMaxValue : maxValue; } else { // 当子串不大于零的时候，子串断裂，开始新的子串。 thisMaxValue = 0; } } System.out.println(maxValue); }
不再解释。
后面还有两种方法没有实现。有兴趣的可以参考这里：http://blog.csdn.net/samjustin1/article/details/52043369
原文：http://www.cnblogs.com/PerkinsZhu/p/6260769.html