《数据结构》01-复杂度1 最大子列和问题

向右看齐 2022-05-08 07:06 138阅读 0赞

# 题目 #

给定K个整数组成的序列\{ N 1 \_1 1, N 2 \_2 2, …, N k \_k k\}，“连续子列”被定义为\{ N i \_\{i\} i , N i + 1 \_\{i+1\} i\+1 , …, N j \_j j \}，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列\{ -2, 11, -4, 13, -5, -2 \}，其连续子列\{ 11, -4, 13 \}有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

*  数据1：与样例等价，测试基本正确性；
 *  数据2：10 2 ^2 2个随机整数；
 *  数据3：10 3 ^3 3个随机整数；
 *  数据4：10 4 ^4 4个随机整数；
 *  数据5：10 5 ^5 5个随机整数；

**输入格式:**  
输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。

**输出格式:**  
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

**输入样例:**

> 6  
> \-2 11 -4 13 -5 -2

**输出样例:**

> 20

# 分析 #

我想到了三种方法，结合老师给的两种，总共五种方法  
先给出 main 函数

int main(){
        
    	int n;
    	int a[100000+5];
    	cin>>n;
    	for(int i=0;i<n;i++)
    		cin>>a[i];
    	MaxSubseqSum1(n,a);
    	MaxSubseqSum2(n,a);
    	MaxSubseqSum3(n,a);
    	MaxSubseqSum4(n,a);
    	MaxSubseqSum5(n,a);
    	return 0;
    }

### 算法一 ###

最直接也是最直观的想法，一个循环控制子列的尾部，内嵌一个循环控制子列的头部，再内嵌一个循环来求解首部到尾部间子列和，每次求解完和更新最大值

/* 方法一：确定子列的首部和尾部，再遍历累加，时间复杂度 O(n^3)*/
    int MaxSubseqSum1(int n,int a[]){
        
    	int max = 0;
    	for(int i=0;i<n;i++){
           // 控制子列的尾部
    		for(int k=0;k<i;k++){
        	  // 控制子列的头部
    			int tmpSum = 0;   //临时存放头部到尾部子列和
    			for(int j=k;j<=i;j++){
           
    				tmpSum+=a[j]; 
    			}
    			if(max < tmpSum)
    				max = tmpSum;
    		}
    	}
    	return max;
    }

容易想到，复杂度也高， O ( n 3 ) O(n^3) O(n3)

### 算法二 ###

考虑优化算法一，观察发现每次计算之后的子列和前面的子列都需要重新计算（比如计算 Sum(n+1)需要重新计算 Sum(n)），那我们可以这样优化，想办法能不能将每次计算的结果保存一下，即一个循环控制子列的首部，内嵌一个循环，既控制子列的尾部，也表示该段子列和，叠加一次更新一次最大值

/* 方法二：确定子列的首部，逐个累加，时间复杂度 O(n^2)*/ 
    int MaxSubseqSum2(int n,int a[]){
        
    	int max = 0;
    	for(int i=0;i<n;i++){
           // 控制子列的首部
    		int tmpSum = 0;  // 当前子列和
    		for(int j=i;j<n;j++){
          // 控制子列的尾部
    			tmpSum+=a[j];
    			if(max < tmpSum)
    				max = tmpSum;
    		}
    	}
    	return max;
    }

把之前控制尾部的循环和求解子列和的循环融合了，复杂度为  O ( n 2 ) O(n^2) O(n2)

### 算法三 ###

想法和算法二类似，不过算法二是控制首部，逐渐累加，算法三是控制尾部，逐渐减值。从首部出发可以自然的用一个数保存整段子列和，而从尾部出发则需要额外数组空间来保存子列和，额外数组空间首先保存其前 n 个数之和，然后每次减去当前值形成子列和

/* 方法三：确定子列的结尾，逐个减去子列前的数，时间复杂度 O(n^2)*/ 
    int MaxSubseqSum3(int n,int a[]){
        
    	int sum[100000+5];
    	int max = 0;
    	sum[0]=a[0];
    	for(int i=1;i<n;i++)   // 预处理保存前 n 个数之和
    		sum[i]=sum[i-1]+a[i];
    	for(int i=0;i<n;i++){
           // 控制尾部
    		int tmpSum = sum[i];
    		for(int j=0;j<=i;j++){
           // 控制首部，每一次减去当前值即首尾子列和
    			if(max < tmpSum)
    				max = tmpSum;
    			tmpSum-=a[j]; 
    		}
    	}
    	return max;
    }

把之前控制首部的循环和求解子列和的循环融合了，复杂度为  O ( n 2 ) O(n^2) O(n2)

### 算法四 ###

“分治法”，简单来说就是把一个大的问题分解成多个小问题求解，再从所有小的解里面寻求最优解。对于此问题而言，可以把一个大的序列分为两个小的序列，再把小的序列分为更小的两个序列，…，直到每个小序列只有一个数，这就是分的过程，在每个小序列中，会得到：

1.  左边最大子列和（正数即本身，负数即0）
2.  右边最大子列和
3.  横跨划分边界的最大子列和

（比如对于只有 1 | 2 两个数的子列，其左边最大子列和为 1 ，右边最大子列和为 2，而横跨划分边界的最大子列和为 1+2）  
此时三者中最大的值就是该小序列的"最大子列和"，以此再得到更高层次的"最大子列和"，…，最终得到整个问题的最大子列和

/* 方法四：递归分成两份，分别求每个分割后最大子列和，时间复杂度为 O(n*logn)*/
    /* 返回三者中最大值*/
    int Max3(int A,int B,int C){
        
    	return (A>B)?((A>C)?A:C):((B>C)?B:C);
    }
    /* 分治*/
    int DivideAndConquer(int a[],int left,int right){
        
    	
    	/*递归结束条件：子列只有一个数字*/
    	// 当该数为正数时，最大子列和为其本身
    	// 当该数为负数时，最大子列和为 0
    	if(left == right){
        
    		if(0 < a[left])  
    			return a[left];
    		return 0;
    	}
    	
    	/* 分别递归找到左右最大子列和*/ 
    	int center = (left+right)/2; 
    	int MaxLeftSum = DivideAndConquer(a,left,center);
    	int MaxRightSum = DivideAndConquer(a,center+1,right);
    	
    	/* 再分别找左右跨界最大子列和*/
    	int MaxLeftBorderSum = 0;
    	int LeftBorderSum = 0;
    	for(int i=center;i>=left;i--){
          //应该从边界出发向左边找
    		LeftBorderSum += a[i];
    		if(MaxLeftBorderSum < LeftBorderSum)
    			MaxLeftBorderSum = LeftBorderSum;	
    	}
    	int MaXRightBorderSum = 0;
    	int RightBorderSum = 0;
    	for(int i=center+1;i<=right;i++){
          // 从边界出发向右边找
    		RightBorderSum += a[i];
    		if(MaXRightBorderSum < RightBorderSum)
    			MaXRightBorderSum = RightBorderSum;
    	}
    	
    	/*最后返回分解的左边最大子列和，右边最大子列和，和跨界最大子列和三者中最大的数*/
    	return Max3(MaxLeftSum,MaxRightSum,MaXRightBorderSum+MaxLeftBorderSum);
    }
    int MaxSubseqSum4(int n,int a[]){
        
    	return DivideAndConquer(a,0,n-1);
    }

时间复杂度  T ( n ) = 2 T ( T 2 ) + c ⋅ n ， T ( 1 ) = O ( 1 ) T(n) = 2T(\\frac \{T\}\{2\}) + c·n ，T(1) = O(1) T(n)=2T(2T)\+c⋅n，T(1)=O(1) ，即  T ( n ) = O ( n l o g n ) T(n) = O(nlogn) T(n)=O(nlogn)

### 算法五 ###

“贪心法”，即不从整体最优上加以考虑，只做出某种意义上的局部最优解。其实最大子列和与它的首部和尾部都没有关系，我们只关心它当前的大小。当临时和加上当前值为负时，它对之后子列和肯定没有帮助（甚至只会让之后的和更小！），我们抛弃这段临时和将它置0

/* 方法五：直接累加，如果累加到当前的和为负数，置当前值或0，时间复杂度为 O(n)*/ 
    int MaxSubseqSum5(int n,int a[]){
        
    	int max = 0;
    	int tmpSum=0;
    	for(int i=0;i<n;i++){
        
    		tmpSum+=a[i];
    		if(tmpSum<0){
        
    			tmpSum=0;
    		}else if(max < tmpSum){
        
    			max = tmpSum;
    		}
    	}
    	return max;
    }

显而易见的，时间复杂度为  O ( n ) O(n) O(n)