学习刘汝佳老师的《算法竞赛》总结
最大连续和问题 给出一个长度为n的序列A 1 ,A 2 ,……,A n ,要求找到1 ≤ i ≤ j ≤ n,使得A i +A i+1 +……+A j 尽量大。 一.使用枚举，程序如下：
tot = 0; best = A[1]; //初始最大值 for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) { //检查连续子序列A[i],……,A[j] int sum = 0; for (int k = i; k <= j; k++) { sum += A[k]; //累加元素和 tot++; } if (sum > best) best = sum; //更新最大值 }设输入规模为n时，加法操作的次数为T(n),则
T(n)=∑i=1n∑j=inj−i+1=∑i=1n(n−i+1)(n−i+2)2=n(n+1)(n+2)6 用一个记号来表示：T(n)=O(n 3 )二.下面试着优化一下这个算法。 设S i =A 1 +A 2 +……+A i ,则A i +A i+1 +……+A j =S j -S i−1 ，其直观含义是”连续子序列之和等于两个前缀和之差“。这样可以省略最内层的循环。
S[0] = 0; for (int i = 1; i <= n; i++) S[i] = S[i - 1] + A[i]; //递推前缀和S for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) best = max(best, S[j] - S[i - 1]); //更新最大值类似的方法可以分析出：
T(n)=∑i=1nn−i+1=n(n+1)2 时间复杂度是O(n 2 ).三.分治法 分治算法一般分为以下三个步骤： 划分问题：把问题的实例划分为子问题； 递归求解：递归解决子问题； 合并问题：合并子问题的解得到原问题的解。 在本例中，”划分“就是把序列尽量分成元素个数相等的两半；”递归求解“就是分别求出完全位于左半和完全位于右半的最佳序列；”合并“就是求出起点位于左半，终点位于右半的最大连续和序列，并和子问题的最优解比较。
int maxsum(int *A, int x, int y) { //返回数组在左闭右开区间[x,y)中的最大连续和 int V, L, R, maxs; if (y - x == 1) return A[x]; int m = x + (y - x) / 2; //分治第一步：划分成[x,m)和[m,y) maxs = max(maxsum(A, x, m), maxsum(A, m, y)); //分治第二步：递归求解 V = 0; L = A[m - 1]; //分治第三步：合并（1）——从分界点开始往左的最大连续和L for (int i = m - 1; i >= x; i--) L = max(L, V += A[i]); V = 0; R = A[m]; //分治第三步：合并（2）——从分界点开始往右的最大连续和R for (int i = m; i <= y; i++) R = max(R, V += A[i]); return max(maxs, L + R); //把子问题的解与L + R比较 }递归方程T(n)=2T(n/2)+O(n),T(1)=1,解为T(n)=O(n log n).
四.算法分析结果 表-运算量随着规模的变化
运算量最大规模速度扩大两倍后n!11112 n 2627n 3 464584n 2 1000014142nlog 2 n4.5x10 6 8.6x10 6 n100000000200000000借鉴此表，在算法竞赛中，一个指明n ≤ 8的题目可能n!的算法已经足够，n ≤ 20的题目需要用到2 n 的算法，而n ≤ 300的题目可能必须用至少n 3 的多项式时间算法了。
