最大子段和
最大子段和一定是每个(准)程序员都接触过的问题，题目很简洁：给出一个长度为 n 的序列a，选出其中连续且非空的一段使得这段和最大。为什么每个(准)程序员都需要掌握呢？首先这问题解法很多，时间复杂度从O(n3) -> O(n2) -> O(nlog2n) -> O(n)。通过解决这个问题可以体会到不同算法的效率差异，其次几种解法中包含分治、前缀和、贪心……等很多算法思想，深入理解最大子段和问题可以举一反三，映射到许多其他问题。
1.暴力 —— O(n3)
最容易想到的方法——枚举，然后就是代码五分钟，运行两小时。
int max = a[0]; // 初始化最大值，不要写 max = 0，因为最大子段和一定为正? for (int i = 0; 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 > max) { // 更新最大子段和 max = sum; } } }
2.暴力 or 前缀和 —— O(n2)
- 上述代码中有很大优化空间，其中最内层循环多次重复计算，每次子段和都只增加一个元素，前面的子段和任然可用，所以可以进行优化。
int max = a[0]; // 初始化最大值，不要写 max = 0，因为最大子段和一定为正? for (int i = 0; i < n; ++i) { // 枚举起始位置 int sum = 0; // 当前子段和初始化 for (int j = i; j < n; ++j) { // 计算当前子段和 sum += a[j]; // 每次在前一子段和基础上增加一个元素 if (sum > max) { // 更新最大子段和 max = sum; } } }
- 使用前缀和，设 Si = A1 + A2 + ··· + Ai，其中 Si就是叫做位置 i 的前缀和。则 Ai + Ai+1 + ··· + Aj = Sj - Si-1，其直观含义是连续子序列之和等于两个前缀和之差。我们可以用这个结论改进 O(n3) 方法的最内层循环。
int max = a[0]; // 初始化最大值，不要写 max = 0，因为最大子段和一定为正? for (int i = 0; i < n; ++i) { // 枚举起始位置 int sum = 0; // 当前子段和初始化 for (int j = i; j < n; ++j) { // 计算当前子段和 sum = i>0?x[j]-x[i-1]:x[j]; // x为前缀和数组，两个前缀和之差，i-1需要大于0，防止数组越界访问 if (sum > max) { // 更新最大子段和 max = sum; } } }
3.分治 —— O(nlog2n)
上述算法虽然优化了内部循环，但是时间复杂度任然不如人意，所以我们尝试使用分治法来解决这个问题。
- 将问题划分为两个规模相同(相近)的子问题。
- 递归解决子问题(分别求出完全位于左半或完全位于右半的最大子段和)。
- 合并子问题的解得到原问题的解(最大子段和将有三种情况——完全位于左半、包含分界点、完全位于右半)。
public static int f(int[] a, int x, int y) { if (y-x == 1) {// 只有一个元素，直接返回 return a[x]; } int mid = x+(y-x)/2; // 分治第一步，划分子问题 int max1 = Math.max(f(a, x, mid), f(a, mid, y));// 分治第二步，递归求解子问题 // 分治第三步，合并子问题的解 int sum = 0; int max2 = a[mid-1]; for (int i = mid-1; i >= x; --i) {// 从分界点开始往左的最大连续和 sum += a[i]; max2 = Math.max(sum, max2); } sum = 0; int max3 = a[mid]; for (int i = mid; i < y; ++i) {// 从分界点开始往右的最大连续和 sum += a[i]; max3 = Math.max(sum, max3); } return Math.max(max1, max2+max3);// 三种情况中的最优解(最大和) }
4.特殊解法 or 前缀和贪心 —— O(n)
- 最大子段和期望以大于 0 的数据开始，所以如果当前位置之前子段和为负则认为重新选择子段头较为合适，从 0 开始计算子段和，记录最大子段和并不断更新。
public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in); int n = in.nextInt();// 元素个数 int sum = 0;// 当前子段和 int max = Integer.MIN_VALUE;// 最大子段和，不应初始化为 0，因为最大子段和有可能为负 for (int i = 0; i < n; ++i) {// 动态处理 int a = in.nextInt();// 读取数据 sum = sum>0?sum:0;// 最大子段和期望以大于 0 开始，小于 0 则重置 sum += a;// 继续计算子段和 max = max>sum?max:sum;// 更新最大子段和 } System.out.println(max);// 输出结果 in.close(); }
- 利用前缀和贪心，Ai + Ai+1 + ··· + Aj = Sj - Si-1，当 j 确定的时候，Sj - Si-1最大等价于 Si-1最小，因此只需要扫描一次数组，维护当前为止遇到过的最小 S 即可（如下代码包含完整输入输出，其中 nextInt() 为自写快读函数，对于大量数据读入更友好，详情见一次由 Scanner(System.in) 引起的 TLE）。
import java.io.*; import java.util.*; public class Main { public static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public static int nextInt() throws IOException { in.nextToken(); return (int)in.nval; } public static void main(String[] args) throws IOException { int n = nextInt();// 快速读数据 int sum = 0; // 记录当前前缀和 int max = Integer.MIN_VALUE; // 记录最大子段和 int min = 0; // 记录当前位置之前最小前缀和 for (int i = 0; i < n; ++i) {// 读取数据同时计算前缀和 sum += nextInt(); // 读取数据同时计算当前前缀和 max = Math.max(max, sum-min); // 当前最大子段和等于当前前缀和减去最小前缀和 min = Math.min(min, sum); // 计算最小前缀和 } System.out.println(max); } }
