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

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

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

(一)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;
}