Loading... 查找一串子列中最大子序列 # 穷举法 ```java public static int maxSubSum1(int[] array) { int maxSum = 0; for (int i = 0; i < array.length; i++) { for (int j = i; j < array.length; j++) { int thisSum = 0; for (int k = i; k < j; k++) { thisSum += array[k]; } if (thisSum > maxSum) { maxSum = thisSum; } } } return maxSum; } ``` 时间复杂度O(n^3) # 穷举法改进 ```java public static int maxSubSum2(int[] array) { int maxSum = 0; for (int i = 0; i < array.length; i++) { int thisSum = 0; for (int j = i; j < array.length; j++) { thisSum += array[j]; if (thisSum > maxSum) { maxSum = thisSum; } } } return maxSum; } ``` 时间复杂度O(n^2) # 分治法 ```java public static int maxSubSum3(int[] array, int left, int right) { // 基准 if (right - left == 1) { if (array[left] > 0) { return array[left]; } return 0; } int centre = (left + right) / 2; int maxLeftSum = maxSubSum3(array, left, centre); int maxRightSum = maxSubSum3(array, centre, right); int maxLeftBorderSum = 0, leftBorderSum = 0; for (int i = centre - 1; i >= left; i--) { leftBorderSum += array[i]; if (leftBorderSum > maxLeftBorderSum) { maxLeftBorderSum = leftBorderSum; } } int maxRightBorderSum = 0, rightBorderSum = 0; for (int j = centre; j < right; j++) { rightBorderSum += array[j]; if (rightBorderSum > maxRightBorderSum) { maxRightBorderSum = rightBorderSum; } } int maxBorderSum = maxLeftBorderSum + maxRightBorderSum; return maxLeftSum > maxRightSum ? (maxLeftSum > maxBorderSum ? maxLeftSum : maxBorderSum) : (maxRightSum > maxBorderSum ? maxRightSum : maxBorderSum); } ``` 时间复杂读O(nlog(n)) # 一种巧妙的方法 ```java public static int maxSubSum4(int[] array) { int maxSum = 0, thisSum = 0; for(int i=0;i<array.length;i++) { thisSum += array[i]; if (thisSum < 0) { thisSum = 0; } else if (thisSum > maxSum){ maxSum = thisSum; } } return maxSum; } ``` 时间复杂度O(n) #### 简要说明正确性 | 分类 | 说明 | | ---- | ------------------------------------------ | | 正数 | 可作为子列的起始,也可以作为子列的结束 | | 负数 | 不可作为子列的起始或结束,只能在子列的中间 | 子列的起始和结束必须是一个正数,负数在子列中间当且仅当thisSum>0时才有意义,否则长度为0的子列也比这个子列大。 最后修改:2020 年 04 月 06 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用,请随意赞赏