首页 > 代码库 > ACM：递归与分治，最大连续和，O(n3), O(n2), O(nlogn), O(n) 算法。

ACM：递归与分治，最大连续和，O(n3), O(n2), O(nlogn), O(n) 算法。

2024-07-10 11:36:25   226人阅读

题目，求一个连续的数组，最大连续和。

（一）O(n3)算法：

利用穷举法的思想，这种方法的效率最差。

代码如下：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;

const int MAXN = 1000;
int A[MAXN], n;

int maxsum(int *A, int n) {
	int beat = A[0];
	for(int i = 1; i <= n; ++i) {
		for(int j = i; j <= n; ++j) {
			int sum = 0;
			for(int k = i; k <= j; ++k) {
				sum += A[k];
			}
			if(sum > best) best = sum;
		}
	}
	return best;
}

int main() {
	cin >> n;
	srand(time(NULL));
	for(int i = 1; i <= n; ++i) {
		A[i] = rand();
	}
	for(int i = 1; i <= n; ++i) cout << A[i] << endl; 
	int maxSumAns = maxsum(A, n);
	cout << maxSumAns << endl;
	return 0;
}

（二）O(n2)算法：

分析：假设Si = A1+A2+...+Ai，则Ai+Ai+1+...+Aj = Sj - Si-1。 这个式子的含义是：连续子序列之和等于两个前缀和之差。

利用这种思想就可以把O(n3)算法里面的最内层的循环给去掉了！

代码如下：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;

const int MAXN = 1000;
int A[MAXN], S[MAXN], n;

int maxsum(int *A, int *S, int n) {
	S[0] = 0;
	int best = A[1];
	for(int i = 1; i <= n; ++i) S[i] = S[i-1] + A[i];
	for(int i = 1; i <= n; ++i) {
		for(int j = i; j <= n; ++j) {
			best = max(best, S[j] - S[i-1]);
		}
	}
	return best;
}

int main() {
	cin >> n;
	srand(time(NULL));
	for(int i = 1; i <= n; ++i) {
		A[i] = rand();
	}
	for(int i = 1; i <= n; ++i) cout << A[i] << endl; 
	int maxSumAns = maxsum(A, S, n);
	cout << maxSumAns << endl;
	return 0;
}



（三）O(nlogn)算法：

分析：利用分治法：

（1）划分问题：把问题的实例划分成子问题。

（2）递归求解：递归解决子问题。

（3）合并问题：合并子问题的解得到原问题的解。

这种方法运用到本例中就是这样的：

（1）划分问题：把序列分成元素个数尽量相等的两半；

（2）递归求解：分别求出完全位于左半或者完全位于右半的最佳序列；

（3）合并问题：求出起点左半、终点位于右半的最大连续和序列，并和子问题的最优解比较。

这里的解法在合并问题步骤时有点特别：既然起点位于左半，终点位于右半，我们可以人为地把这样的序列分成两部分，然后独立求解：先寻找最佳起点，然后再寻找最佳终点。


代码如下：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;

const int MAXN = 1000;
int A[MAXN], n;

int maxsum(int *A, int x, int y) {   //返回数组在左闭右开区间[x, y)中的最大连续和
	if(y - x == 1) return A[x];  //只有一个元素，直接返回
	int m = x + (y - x) / 2;   //分治第一步：划分成[x, m)和[m, y)。
	int maxans =  max(maxsum(A, x, m), maxsum(A, m, y));  //分治第二部，递归求解，左边的最大连续和以及右边的最大连续和，两者更大的那个放进变量maxans中
	int L = A[m-1], u = 0;
	for(int i = m-1; i >= x; --i) L = max(L, u += A[i]);  //分治第三部，合并（1）—从分界点开始往左的最大连续和L
	int R = A[m], v = 0;
	for(int i = m; i < y; ++i) R = max(R, v += A[i]);  //分治第三部，合并（2）—从分界点开始往右的最大连续和R
	return max(maxans, L+R);  //把子问题的解与L和R比较
}

int main() {
	cin >> n;
	srand(time(NULL));
	for(int i = 1; i <= n; ++i) {
		A[i] = rand();
	}
	int maxSumAns = maxsum(A, 1, n+1);
	for(int i = 1; i <= n; ++i) cout << A[i] << endl; 
	cout << maxSumAns << endl;
	return 0;
}

（四）O(n)算法：

对O(n2)的算法稍作改进，就可以得到下面这种最高效的算法了！

分析：当j确定时，“S[j] - S[i-1]最大”，相当于“S[i-1]最小”，因此只需要扫一次数组，维护“目前遇到过的最小S”即可！！！

代码如下：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;

const int MAXN = 1000;
int A[MAXN], S[MAXN], n;

int maxsum(int *A, int *S, int n) {
	S[0] = 0;
	for(int i = 1; i <= n; ++i) S[i] = S[i-1] + A[i];
	int mins = S[0], maxs = -100000;
	for(int i = 1; i <= n; ++i) {
		if(S[i] - mins > maxs) maxs = S[i] - mins;
		if(S[i] < mins) mins = S[i];      //维护“目前遇到过的最小S”
	}
	return maxs;
}

int main() {
	cin >> n;
	srand(time(NULL));
	for(int i = 1; i <= n; ++i) {
		A[i] = rand();
	}
	for(int i = 1; i <= n; ++i) cout << A[i] << endl; 
	int maxSumAns = maxsum(A, S, n);
	cout << maxSumAns << endl;
	return 0;
}


联系
我们