数据结构与算法 / 系统课时
分治算法设计流程
分治算法设计流程
最大子数组问题要求在整数数组中找到一个非空连续区间,使其元素和最大。本课按拆分、求解、合并、证明和成本分析实现这个问题,保留区间端点以便验证结果。
学习目标
- 写清分治的输入、输出、基础情形与较小子问题。
- 证明最优区间覆盖左侧、右侧和跨中点三种情形。
- 用实际整数递推和调用深度分析当前实现。
先定契约,再设计合并
输入为非空 int[],返回 0 起始的闭区间端点以及区间和。若存在多个最优区间,返回其中一个即可。子问题用当前闭区间 [low, high] 表示,不复制数组。单元素区间只能选该元素,所以全负数组也能正确处理。 UCLA 算法课程最大子数组

拆成 [low, mid] 和 [mid+1, high] 后,任意非空连续区间只可能完全在左、完全在右,或同时包含 mid 和 mid+1。前两类用递归解决。跨界区间必由左半的一个非空后缀与右半的一个非空前缀拼成,两部分可独立选择。分别扫描得到最大后缀与前缀,相加便得到这一类的最优解。按规模归纳,两个子问题的结果正确,再取三类最大值即可得到整个区间最优。 UCLA 算法课程跨中点方法
Java 17 实现
将代码保存为 MaximumSubarrayDivideConquer.java。本课沿用 Java 示例,需要 JDK 17 或以上。区间和使用 long,避免多个较大 int 相加时 32 位溢出。Java 数组长度与下标使用 int,在合法 int[] 范围内,元素和也不会超出 long 范围。 Java 整数类型规格
import java.util.Arrays;
import java.util.Objects;
public class MaximumSubarrayDivideConquer {
public record Result(int start, int end, long sum) {}
public static Result findMaximumSubarray(int[] values) {
Objects.requireNonNull(values, "values");
if (values.length == 0) {
throw new IllegalArgumentException("expected a non-empty array");
}
return solve(values, 0, values.length - 1);
}
private static Result solve(int[] values, int low, int high) {
if (low == high) {
return new Result(low, high, values[low]);
}
int mid = low + (high - low) / 2;
Result left = solve(values, low, mid);
Result right = solve(values, mid + 1, high);
Result cross = crossing(values, low, mid, high);
Result best = right.sum() > left.sum() ? right : left;
return cross.sum() > best.sum() ? cross : best;
}
private static Result crossing(int[] values, int low, int mid, int high) {
long sum = 0;
long leftBest = Long.MIN_VALUE;
int start = mid;
for (int i = mid; i >= low; i--) {
sum += values[i];
if (sum > leftBest) {
leftBest = sum;
start = i;
}
}
sum = 0;
long rightBest = Long.MIN_VALUE;
int end = mid + 1;
for (int i = mid + 1; i <= high; i++) {
sum += values[i];
if (sum > rightBest) {
rightBest = sum;
end = i;
}
}
return new Result(start, end, leftBest + rightBest);
}
public static void main(String[] args) {
int[] values = {13, -3, -25, 20, -3, -16, -23, 18,
20, -7, 12, -5, -22, 15, -4, 7};
Result result = findMaximumSubarray(values);
System.out.println("最大子数组起始下标: " + result.start());
System.out.println("最大子数组结束下标: " + result.end());
System.out.println("最大子数组和: " + result.sum());
System.out.println("最大子数组: "
+ Arrays.toString(Arrays.copyOfRange(values, result.start(), result.end() + 1)));
}
}在命令行执行 javac -encoding UTF-8 --release 17 MaximumSubarrayDivideConquer.java,再执行 java MaximumSubarrayDivideConquer。
最大子数组起始下标: 7
最大子数组结束下标: 10
最大子数组和: 43
最大子数组: [18, 20, -7, 12]成本与复核
规模大于 1 时,左侧长度为 ,右侧为 ,合并线性扫描。递推为 。按第 04-05 节的逐层上下界得到 ;当 为 2 的幂,也可直接用主定理。递归栈以及每层同时需要的结果记录占 额外空间。演示打印时单独复制结果片段,这部分不计入求解函数。通过在递归结果里保存更多摘要,可以设计不同的合并成本,本课结论针对逐层扫描实现。 MIT 递推与取整 线性分治最大子数组研究
本课练习
测试单元素、全负、奇数长度、并列最大和以及两个 Integer.MAX_VALUE 相邻的情况。用两层循环枚举起止点作为小输入对照,比较最大和并核对端点对应的实际和值。下一章进入线性数据结构,从数组访问、插入和删除开始。