题目
给定K个整数组成的序列{ N 1, N 2, …, N k}，“连续子列”被定义为{ N i , N i+1 , …, N j }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：
- 数据1：与样例等价，测试基本正确性；
- 数据2：10 2个随机整数；
- 数据3：10 3个随机整数；
- 数据4：10 4个随机整数；
- 数据5：10 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(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(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(n2)
算法四
“分治法”，简单来说就是把一个大的问题分解成多个小问题求解，再从所有小的解里面寻求最优解。对于此问题而言，可以把一个大的序列分为两个小的序列，再把小的序列分为更小的两个序列，…，直到每个小序列只有一个数，这就是分的过程，在每个小序列中，会得到：
- 左边最大子列和（正数即本身，负数即0）
- 右边最大子列和
- 横跨划分边界的最大子列和
（比如对于只有 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)=2T(2T)+c⋅n，T(1)=O(1) ，即 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)
京公网安备 11010502036488号