最大连续子数组，动态规划经典问题

动态规划（Dynamic Programming）其中的 Programming指的是一种表格法。 相较于分治，动态规划主要应用于子问题重叠的情况。 重点是找出最优子结构

---

最大连续子数组问题：

一、 问题描述

二、 几种解决方法：

1 暴力枚举:

最简单也是最耗时的做法就是对其进行枚举，为了找全所有的连续子数组，我们看看至少需要几层循环： 对一个连续的子数组$A[l..r]$, $r$表示子数组右边的坐标，$l$表示左边的

int smax = -inf; for(int r = 0; r < n; ++r) { // 枚举右端点 for (int l = 0; l <= r; ++l) { // 枚举左端点 int sum = 0; // 表示子数组A[l..r]的和 for (int i = l; i <= r; ++i) { // 对[l,r]遍历求和 sum += A[i]; // } if(sum > smax) smax = sum; //if .... } }

一共有多少种呢： $n+C_n^2$

所以需要三重循环，时间复杂度应该是$O(n^3)$，这种做法做了等于没做，还不如不做。接下来想一想怎么对其优化。

枚举之所以时间复杂度高，是因为它在三重循环的过程中，实际上重复计算了很多元素。 例如：某一步中我们已经求了连续子数组$A[1..6]$的和，做了一次从$A[1]$ 到$A[6]$的遍历，当我们想求$A[1..7]$的时候，我们又遍历了一遍$A[1..6]$，这样就对$A[1..6]$的遍历做了重复。

容易想到的一个优化的思路就是记录下每次遍历得到的值，如果需要对这一块再次遍历时，就直接拿出来用，就可以避免掉一次的重复。

2 优化枚举

核心思想： $S(l,r)={\sum }_{l\le i\le r}A[i]=S(l,r-1)+A[r]$

int smax = -inf; for (int l = 0; l < n; ++l){ int s = 0; for (int r = l; r < n; ++r) { s = s + A[r]; //当前的s=sum(A[l..r]) = s(A[l..r-1]) + A[r] smax = max(smax, s); // } }

两重循环，时间复杂度为$O(n^2)$

即使这样做了，中间还是有重复计算的： 比如：计算$S(1,6)$ 和 计算 $S(2,7)$， 两个都对$S(2,6)$进行了重复的遍历求和。

所以优化枚举虽然使得每个$S(l,r)$只用一次for就解决了，但是不同的$S(l_i,r_i)$之间还是有一些不必要的重复计算。导致了时间复杂度比较高。

想要进一步降低时间复杂度该怎么办呢？

3 分治算法

为了采用分治算法，我们要将原问题分解为两个规模尽量相等的子问题，分别求解。 也就是将原数组分解成两个大小尽量相等的子数组，对这两个子数组分别求解其最大连续子数组。 然后还要注意的是，还要求出跨中间分界线的最大连续子数组和是多少。 假设$A[1...n]$ ，$mid=\frac{n}{2}$, 将原数组分解成两个子数组： $A[1..mid]$(最大子数组和为$S_l$) 和$A[(mid+1)...n]$(最大子数组和为$S_r$), 跨越$mid$的最大子数组和为$S_{mid}$，那么整体的最大子数组和应该是$max(S_l,S_r,S_{mid})$

我自己写的有点乱，看看课件有条理的分析：

伪代码：

主伪代码

跨中间的连续最大子数组的和 伪代码，来自《算法导论》

代码实现：（先鸽着，重点是写dp！）

\\咕咕咕

3 动态规划

靠，写了一个小时才写到重点…, 不过自己一步一步思考从从哪里得到的优化思路还是很有收获的。废话少说，赶紧总结完去写别的作业。

用$D[i]$ 表示以A[i]开头的连续最大子数组的和

(怎么想到的？我也不知道now…)，

那么可以得到一个递推方程(即状态转移方程)：

// 初始化： for (int i = 0; i < n; ++i) D[i] = A[i]; // 既然D[i]是以A[i]开头的balabala，那么D[i]肯定要包含A[i] // 至于加不加上D[i+1]，要看D[i+1]加上之后能不能使D[i]变大 if(D[i+1] > 0) D[i] = D[i+1] + A[i]; else D[i] = A[i];

由于这个方程是由$D[i+1]$得到$D[i]$，那么我们遍历要从后往前遍历： (或者你就用$D[i]$表示以$A[i]$为结尾的连续最大子数组的和，这样就是从前往后遍历)

伪代码：

这里是用Rec[i] 记录解的位置，然后再返回去查找连续最大子数组的左右下标，好好学习一下

显然时间复杂度为$O(n)$, NB!!!

开头说了，DP中的P是指表格，也就是D[i], 这个问题比较简单，就是一个一维的表格。

代码实现

// 洛谷P1115 最大子段和 #include <iostream> using namespace std; int D[200010], A[200010], Rec[200010]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> A[i]; } // 初始化 D[n] = A[n]; Rec[n] = n; // 递推 for (int j = n - 1; j > 0; j--) { if(D[j+1] > 0) { D[j] = A[j] + D[j+1]; Rec[j] = Rec[j+1]; // Rec[j] 记录的是以A[j] 开始的最大连续子数组 右端点的下标 } else { D[j] = A[j]; Rec[j] = j; } } int smax = D[n], l=0, r=0; for (int i = 1; i <= n; ++i) { if (D[i] > smax) { smax = D[i]; l = i; r = Rec[i]; } } cout << smax; return 0; }