前言
最近回溯算法，对以往算法和新学习算法进行一个系统的整理和学习，本文的最大子序列和的问题在很多算法书籍和技术文章中对此都有详述，个人简单整理仅为了再次消化和日后查阅，不喜误喷。个人理解，如有错误，欢迎指正。
注：本文中提及的时间复杂度均使用大O法。
问题描述
求-2,4,-1,5,6的最大子序列和
注：如果所有值都为负，则最大子序列和为0
方案一
- 思路：使用穷举的方式，使用for循环列出所有的子序列进行求和，每次进行对比并把大的数赋值给最大子序列和变量，总共使用三个for循环 注：i循环为从-2到6（头到尾），j循环为i到此序列size，k为计算此时i到此时j的子序列和
- 源码如下：
//穷举遍历法 三个for循环时间复杂度为n*n*n 十分低效 public static int maxSubSum1(int[] array) { int maxSubSum = 0; for (int i = 0; i < array.length; i++) { for (int j = i; j < array.length; j++) { int curSum = 0; for (int k = i; k <= j; k++) { curSum += array[k]; if (curSum > maxSubSum) { maxSubSum = curSum; } } } } return maxSubSum; }
方案二
- 思路：maxSubSum1中k到j是前面加到后面求和，而这里是以i为指针基点，往后求和，减少一个for循环（k）时间复杂度为n*n
- 源码：
public static int maxSubSum2(int[] array) { int maxSubSum = 0; for (int i = 0; i < array.length; i++) { //tmp 变量在上面for循环每次必须重新初始化 int tmpSum = 0; for (int j = i; j < array.length; j++) { //maxSubSum1中k到j是前面加到后面求和，而这里是以i为指针基点，往后求和 tmpSum += array[j]; if (tmpSum > maxSubSum) { maxSubSum = tmpSum; } } } return maxSubSum; }
方案三
- 思路 时间复杂度为nlogn的解法，使用分治策略和递归。主要把数组从中间分开，然后左边和右边递归求这两部分的最大子序列和，中间界限的最大子序列和为左边包含最接近中间的最大子序列和，以及右边包含最接近中间的最大子序列和的左右这两个最大子序列之和。最后比较这三部分的最大子序列和，其中最大的即为最大子序列和。时间复杂度为nlogn。
- 源码
/** * 递归分治算法 * @param array * @return */ //test (13/2 (6/2 ( 3/2 ( 1/2 ( 0 ) syso 1 ) syso 1 ) syso 0 ) ) syso 1 //maxSubSum3 (array,0,4 (array,0,2 (array,0,1 (array,0,0[return]反过来执行后续代码，递归的递归[maxSubSum3(array,center+1,right)]这个)))) public static int maxSubSum3(int[] array,int left,int right) { //此时左边界和右边界相等，该数组只有一个数，判断是否为负数，直接返回 if (left == right){ return array[left] > 0 ? array[left] : 0; } //二分 //二进制右移位一次，为除法的除以2，但是效率比较高 int center = (left+right)>>1; //递归左部分 int maxSubLeftSum = maxSubSum3(array,left,center); //递归右部分 int maxSubRightSum = maxSubSum3(array,center+1,right); //临近中间的左部分最大子序列和 curLeftBorderTmpSum 边界临时值 int maxLeftBorderSum = 0, curLeftBorderTmpSum = 0; //左中部分 从center开始向左求和（必须包含array[center]） 找出最大值 for(int i = center;i >= left; i--){ curLeftBorderTmpSum += array[i] ; if(curLeftBorderTmpSum > maxLeftBorderSum) maxLeftBorderSum = curLeftBorderTmpSum; } //临近中间的右部分最大子序列 curRightBorderTmSum 边界临时值 int maxRightBorderSum = 0, curRightBorderTmSum = 0; //右中部分 从center开始向右求和（必须包含array[center]） 找出最大值 for(int i = center+1; i <= right;i++){ curRightBorderTmSum += array[i]; if(curRightBorderTmSum > maxRightBorderSum) maxRightBorderSum = curRightBorderTmSum; } //返回最大子序列和 int temp = Math.max(maxSubLeftSum, maxSubRightSum); return Math.max(temp, maxRightBorderSum+maxLeftBorderSum); }
方案四
- 思路： 如果a[i]为负，则不可能是最大子序列的起点，因为此时的所谓序列可以通过ai+1，来得到改进;任何负的子序列不可能是最大子序列的前缀，原理同上。循环一次，直接用i作为基点，连续相加，找出最大的即可 时间复杂度为n
- 源码：
/** * 最优算法，O（n） * @param array * @return */ public static int maxSubSum4(int[] array){ int maxSubSum = 0, curTmpSum = 0; for (int i = 0; i < array.length; i++){ curTmpSum += array[i]; if(curTmpSum > maxSubSum){ maxSubSum = curTmpSum; }else if(curTmpSum < 0){ curTmpSum = 0; } } return maxSubSum; }
完整源码
```
package com.anteoy.coreJava.tmp;
/**
* Created by zhoudazhuang
* Date: 17-3-29
* Time: 上午10:40
* Description : 求最大子序列和
*/
public class Test {
//穷举遍历法 三个for循环时间复杂度为n*n*n 十分低效
public static int maxSubSum1(int[] array) {
int maxSubSum = 0;
for (int i = 0; i < array.length; i++) {
for (int j = i; j < array.length; j++) {
int curSum = 0;
for (int k = i; k <= j; k++) {
curSum += array[k];
if (curSum > maxSubSum) {
maxSubSum = curSum;
}
}
}
}
return maxSubSum;
}
public static int maxSubSum2(int[] array) {
int maxSubSum = 0;
for (int i = 0; i < array.length; i++) {
//tmp 变量在上面for循环每次必须重新初始化
int tmpSum = 0;
for (int j = i; j < array.length; j++) {
//maxSubSum1中k到j是前面加到后面求和，而这里是以i为指针基点，往后求和
tmpSum += array[j];
if (tmpSum > maxSubSum) {
maxSubSum = tmpSum;
}
}
}
return maxSubSum;
}
/**
* 递归分治算法
* @param array
* @return
*/
//test (13/2 (6/2 ( 3/2 ( 1/2 ( 0 ) syso 1 ) syso 1 ) syso 0 ) ) syso 1
//maxSubSum3 (array,0,4 (array,0,2 (array,0,1 (array,0,0[return]反过来执行后续代码，递归的递归[maxSubSum3(array,center+1,right)]这个))))
public static int maxSubSum3(int[] array,int left,int right) {
//此时左边界和右边界相等，该数组只有一个数，判断是否为负数，直接返回
if (left == right){
return array[left] > 0 ? array[left] : 0;
}
//二分
//二进制右移位一次，为除法的除以2，但是效率比较高
int center = (left+right)>>1;
//递归左部分
int maxSubLeftSum = maxSubSum3(array,left,center);
//递归右部分
int maxSubRightSum = maxSubSum3(array,center+1,right);
//临近中间的左部分最大子序列和 curLeftBorderTmpSum 边界临时值
int maxLeftBorderSum = 0, curLeftBorderTmpSum = 0;
//左中部分 从center开始向左求和（必须包含array[center]） 找出最大值
for(int i = center;i >= left; i--){
curLeftBorderTmpSum += array[i] ;
if(curLeftBorderTmpSum > maxLeftBorderSum)
maxLeftBorderSum = curLeftBorderTmpSum;
}
//临近中间的右部分最大子序列 curRightBorderTmSum 边界临时值
int maxRightBorderSum = 0, curRightBorderTmSum = 0;
//右中部分 从center开始向右求和（必须包含array[center]） 找出最大值
for(int i = center+1; i <= right;i++){
curRightBorderTmSum += array[i];
if(curRightBorderTmSum > maxRightBorderSum)
maxRightBorderSum = curRightBorderTmSum;
}
//返回最大子序列和
int temp = Math.max(maxSubLeftSum, maxSubRightSum);
return Math.max(temp, maxRightBorderSum+maxLeftBorderSum);
}
/**
* 最优算法，O（n）
* @param array
* @return
*/
public static int maxSubSum4(int[] array){
int maxSubSum = 0, curTmpSum = 0;
for (int i = 0; i < array.length; i++){
curTmpSum += array[i];
if(curTmpSum > maxSubSum){
maxSubSum = curTmpSum;
}else if(curTmpSum < 0){
curTmpSum = 0;
}
}
return maxSubSum;
}
public static void main(String[] args) {
//计算耗时，需要提供一个较大的数组，否则看不出差距 或者使用 System.nanoTime()毫微秒
int[] array = {-2,4,-1,5,6};
Long time1 = System.nanoTime();
int maxSubSum1 = maxSubSum1(array);
System.out.println("maxSubSum1计算结果： " + maxSubSum1 + "\n" + "耗时" + (System.nanoTime() - time1));
Long time2 = System.nanoTime();
int maxSubSum2 = maxSubSum2(array);
System.out.println("maxSubSum2计算结果： " + maxSubSum2 + "\n" + "耗时" + (System.nanoTime() - time2));
Long time3 = System.nanoTime();
int maxSubSum3 = maxSubSum3(array,0,array.length -1);
System.out.println("maxSubSum3计算结果： " + maxSubSum3 + "\n" + "耗时" + (System.nanoTime() - time3));
}
}
```
参考文献
《数据结构与算法分析》
