数据结构与算法 / 系统课时

分治算法设计流程

分治算法设计流程

最大子数组问题要求在整数数组中找到一个非空连续区间,使其元素和最大。本课按拆分、求解、合并、证明和成本分析实现这个问题,保留区间端点以便验证结果。

学习目标

  • 写清分治的输入、输出、基础情形与较小子问题。
  • 证明最优区间覆盖左侧、右侧和跨中点三种情形。
  • 用实际整数递推和调用深度分析当前实现。

先定契约,再设计合并

输入为非空 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 整数类型规格

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。

text
最大子数组起始下标: 7
最大子数组结束下标: 10
最大子数组和: 43
最大子数组: [18, 20, -7, 12]

成本与复核

规模大于 1 时,左侧长度为 ⌈n/2⌉\lceil n/2\rceil,右侧为 ⌊n/2⌋\lfloor n/2\rfloor,合并线性扫描。递推为 T(n)=T(⌊n/2⌋)+T(⌈n/2⌉)+Θ(n)T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n)。按第 04-05 节的逐层上下界得到 Θ(nlog⁡n)\Theta(n\log n);当 nn 为 2 的幂,也可直接用主定理。递归栈以及每层同时需要的结果记录占 Θ(log⁡n)\Theta(\log n) 额外空间。演示打印时单独复制结果片段,这部分不计入求解函数。通过在递归结果里保存更多摘要,可以设计不同的合并成本,本课结论针对逐层扫描实现。 MIT 递推与取整 线性分治最大子数组研究

本课练习

测试单元素、全负、奇数长度、并列最大和以及两个 Integer.MAX_VALUE 相邻的情况。用两层循环枚举起止点作为小输入对照,比较最大和并核对端点对应的实际和值。下一章进入线性数据结构,从数组访问、插入和删除开始。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

分治算法设计流程

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通