鸿蒙 PC 三方库适配复盘：tiny-regex-c —— 当上游 Makefile 根本不产出库

wdracky

588人浏览 · 2026-10-12 10:43:34

wdracky · 2026-10-12 10:43:34 发布

摘要

本文复盘把 tiny-regex-c（Rob Pike 正则思路的 C 实现，两个文件、530 行）适配进鸿蒙 PC 生态的完整过程。选它是因为它把三方库适配最容易踩的三个坑一次性集齐：上游 make 不产出库（all 只编五个测试可执行文件，配方必须绕开 make 直接调编译器编 re.c）、上游没有任何 tag（只能按完整 commit 钉版，用 cci.20241025 并写进 source.note）、上游语义反直觉且不能"顺手修正"（记号上限静默截断、静态缓冲区单例、类内转义一轮吃掉两个字符等六条语义全部原样保留并写成断言）。配套给出 19 条 CHECK 的 test_package、把 re_compile 中间产物摊在屏幕上的 ArkTS Demo（逐行复刻引擎并补 truncated 标志），以及 C 消费者测试 → ArkTS 逻辑测试 → 本地 Node 对拍的三层同向量验证。全部开发在 DevEco Studio 26 上完成，文末附复现命令、可复用经验清单，以及一道面试常被追问的最大子数组分治解法（O(n log n)）与对撞验证结果。

一、为什么选它
二、坑一：make 不会给你一个库
三、坑二：没有 tag，版本号怎么写
四、坑三：上游语义反直觉，而且不能"顺手修正"
五、test_package：19 条断言，一半用来钉死反直觉语义
六、Demo：把"看不见的适配"摊在屏幕上
七、开发环境：DevEco Studio 26 上的完整开发链路
八、复现命令
九、可复用的经验清单
十、附：最大子数组的分治解法（O(n log n)）

一、为什么选它

tiny-regex-c 是 Rob Pike《A Regular Expression Matcher》那套思路的 C 实现：两个文件、
530 行，re_compile() 把模式串编译成一个记号数组，re_matchp() 用指针在文本上滑动加回溯。
支持 . ^ $ * + ?、[abc]、[a-z]、[^abc]、\d \D \w \W \s \S，不支持 {n,m}、分支 |、
捕获组、懒惰量词。

在鸿蒙 PC 上它有一类很具体的用途：输入框校验、命令白名单、日志行过滤这类「只需要知道
有没有、从哪开始、有多长」的场景。为此把 900 KB 的 PCRE 拖进 HAP 是不划算的 ——
这个库的 .a 只有 8 KB 出头（re.o 8744 字节）。

但选它不是为了"小"，而是因为它把三方库适配里最容易踩的三个坑一次性集齐了：
上游构建系统不产出库、上游没有任何 tag、上游语义反直觉且不能"顺手修正"。
下面逐条复盘，每一条都有对应的 PR 文件与可运行的验证方式。

二、坑一：`make` 不会给你一个库

这是本次适配的第一个"意外"。大多数 C 库的 Makefile 至少有 libxxx.a 或 install，
而 tiny-regex-c 的 Makefile 非常朴素：

CC := gcc
CFLAGS := -O3 -Wall -Wextra -std=c99 -I.

all:
	@$(CC) $(CFLAGS) re.c tests/test1.c         -o tests/test1
	@$(CC) $(CFLAGS) re.c tests/test2.c         -o tests/test2
	@$(CC) $(CFLAGS) re.c tests/test_rand.c     -o tests/test_rand
	@$(CC) $(CFLAGS) re.c tests/test_rand_neg.c -o tests/test_rand_neg
	@$(CC) $(CFLAGS) re.c tests/test_compile.c  -o tests/test_compile

all 只编译五个测试可执行文件：没有库目标、没有 install 规则、没有 prefix 变量。
如果配方按"惯例"写 self.run("make")，conan 打包阶段会得到一堆 .exe/ELF 测试程序，
package() 里 include/ 和 lib/ 一个文件都复制不进去 —— 而且 make 是成功的，
错误发生在更后面的 package_info()，排查链路很长。

结论：配方必须绕开 make，直接调编译器编 re.c。核心逻辑：

cc = self._compiler()                     # 取自 tools.build:compiler_executables['c']
obj = os.path.join(self.build_folder, "re.o")

cflags = ["-std=c99", "-Wall", "-Wextra"]
if str(self.settings.os) == "OHOS":
    target = self._ohos_target()          # aarch64-linux-ohos
    cflags.append(f"--target={target}")
    sysroot = self._sysroot()
    if sysroot:
        cflags.append(f"--sysroot={sysroot}")
    ldflags.extend([x for x in cflags if x.startswith("--")])

cflags.append("-O3" if str(self.settings.build_type) == "Release" else "-O0 -g")
cflags.append("-fPIC")                     # 静态库也要，消费者可能把它链进 .so

self.run(f'"{cc}" {cflags_str} -I "{self.source_folder}" -c '
         f'"{self.source_folder}/re.c" -o "{obj}"')

三个细节值得单独说：

细节	做法	为什么
编译器来源	`tools.build:compiler_executables['c']`	上游把 `CC := gcc` 写死；release worker 上没有 gcc，也没有 `$CC`，沿用 make 会在「命令成功」的假象下产出宿主架构的目标文件
库名	`libtinyregexc`（去掉连字符）	`-l` 参数里出现 `-` 时不同链接器处理不一致；同时 `cmake_file_name` / `cmake_target_name` 统一成 `tinyregexc`，消费者写 `find_package(tinyregexc)`
OHOS 参数	`--target` / `--sysroot` 同时进 cflags 与 ldflags	只进 cflags 时，CMake/Conan 的链接探针仍拿宿主三元组去链 aarch64 目标文件，产物会被静默替换

另外两条是通用经验，本文不展开（前面几篇已写过）：shared=True 的 .so 必须
binary-sign-tool sign -selfSign 1 自签名；validate() 用
self.settings.os in ("Linux", "OHOS")，不能写 == "Linux"。

三、坑二：没有 tag，版本号怎么写

curl.exe -s https://api.github.com/repos/kokke/tiny-regex-c/tags
# []

[]。上游从 2013 年至今没打过任何 tag，master 最新提交是
f2632c6d9ed25272987471cdb8b70395c2460bdb（2024-10-25）。这直接决定了两件事：

1）版本目录名。仓内已有先例 archives/a/andreasbuhr-cppcoro/cci.20230629，约定是
cci.<commit 日期>。所以本次用 cci.20241025（提交日期，不是提交当日时间戳）。

2）源地址必须钉到 commit。Codeload 支持任意 commit：

# conandata.yml
sources:
  "cci.20241025":
    url: "https://codeload.github.com/kokke/tiny-regex-c/tar.gz/f2632c6d9ed25272987471cdb8b70395c2460bdb"
    sha256: "a79fe8748a56023c800a8e7356d30fee503f3e1ba4a69aca9d892b4a8bb18fa3"

sha256 是把这个 commit 的 tarball（53442 字节）实算出来的，不是抄来的。不能用
.../tar.gz/refs/heads/master：master 一移动，conan create 就会拉到不同源码，
而 sha256 校验会失败 —— 报错信息是"下载校验不通过"，看起来像网络问题，实际是源地址没钉住。

三种钉版方式的取舍：

方式	可复现性	适用场景
`refs/tags/<ver>`	强	上游有 tag（首选）
`refs/heads/master` + sha256	中（sha256 兜底，但报错难定位）	上游无 tag 且允许失败重试
完整 commit + `cci.<日期>`	强	上游无 tag（本文采用，仓内已有先例）

manifest.yaml 里把这件事写进 source.note 与 knowledge_gained，reviewer 不必再问
“为什么版本号不是 semver”：

version: "cci.20241025"
source:
  pinned_commit: "f2632c6d9ed25272987471cdb8b70395c2460bdb"
  note: "上游 GitHub tags 为空，只能按 commit 钉版；cci.<commit 日期> 与仓内 andreasbuhr-cppcoro/cci.20230629 同约定"

四、坑三：上游语义反直觉，而且不能"顺手修正"

适配三方库最容易犯的错，是在"我觉得这里应该是 bug"的地方改上游源码。改完测试也过了，
但产物行为已经和上游二进制不一致 —— 下游消费者按上游文档写的代码会在鸿蒙上崩。

tiny-regex-c 有六条这样的语义，全部原样保留，并在 notes.md 里列成表：

语义	上游实现	现象
记号上限	`while (pattern[i] && j+1 < MAX_REGEXP_OBJECTS)`，`MAX_REGEXP_OBJECTS = 30`	第 30 个记号起静默丢弃，不报错、不返回 NULL
静态缓冲区	`re_compiled[30]` / `ccl_buf[40]` 定义在 `re.c` 内部	单例：第二次 `re_compile` 覆盖第一次的结果，不能跨线程共用
字符类上限	整个表达式所有字符类共享 40 字节缓冲，且每个类还要写一个 `'\0'`	超长类返回 NULL（不是截断）
空串语义	`re_matchp` 里 `if (text[0] == '\0') return -1`	`.?` 匹配空串返回 -1（长度 0），而不是"在 0 处命中空串"
结尾反斜杠	`case '\\'` 里 `pattern[i+1] != '\0'` 才产生记号	`"ab\"` 等价于 `"ab"`，被静默忽略
类内转义	转义分支先 `str += 1`，`while (*str++)` 再前进一格	一轮转义吃掉两个字符：`[\d]` 的 ‘d’ 是转义类名，所以 `[\d]` 不匹配 `"d"`

前五条可以用"照抄上游"的态度躲过去，第六条是真的会咬人的 —— 我自己的第一次移植就写错了。

4.1 类内转义为什么会吃掉两个字符

matchcharclass() 的循环是 do { ... } while (*str++ != '\0')，而转义分支里还有一次自增：

do {
  if (matchrange(c, str))            return 1;
  else if (str[0] == '\\') {
    str += 1;                        /* ① 指针挪到被转义的字符上 */
    if (matchmetachar(c, str)) return 1;
    else if ((c == str[0]) && !ismetachar(c)) return 1;
  }
  else if (c == str[0]) { ... }
} while (*str++ != '\0');            /* ② 再前进一格 */

对 [\d]（类内容缓冲为 "\\d"）匹配文本 "d"：

第 1 轮：str[0] == '\\' → ① 前进到 'd'；matchmetachar('d', "d") → matchdigit('d') 为假；
接着 c == str[0]（'d' == 'd'）但 ismetachar('d') 为真 → 不算字面量；
② 前进一格 → str 指向 \0；
第 2 轮：三个分支都不成立，② 终止 → 返回 0。

如果移植时只前进一格（少算了 ②），第 2 轮就会把 'd' 当成普通字符比较，
[\d] 于是匹配上了 "d" —— 结果是"看起来能用"，但和 C 侧不一致。

我是在本地断言里加上这条才抓到的（当时 29 条断言里唯一一条 FAIL）：

FAIL [\d] must not match literal d
tiny-regex-c ArkTS port: 30 checks, 1 failures

修正后的 ArkTS 实现照抄了两次自增：

if (s0 === '\\') {
  const esc: string = (p + 1) < cls.length ? cls.charAt(p + 1) : '';  // 对应 ①
  if (matchMetaChar(c, esc)) return true;
  if (c === esc && !isMetaEscape(c)) return true;
  if (esc === '') return false;   // 类以孤立反斜杠结尾
  p += 2;                         // ① + ② 一共两格
  continue;
}

这条经验的可复用版本是：*凡是 C 里用「指针 + do-while(p++)」写的扫描循环，移植时先数清楚
每轮到底自增了几次，别按"一次循环前进一格"的直觉写。

五、test_package：19 条断言，一半用来钉死反直觉语义

test_package/test.c 不是复刻上游 tests/test1.c，而是验证「装进 include/ + lib/ 之后
消费者还能正确用」。19 条 CHECK 分三组：

组	断言	目的
基础向量	`\d`、`\w+`、`\s`、`[0-9]+`、`^\d+$` 成功/失败、`[a-z]+` 偏移 2 长度 3、`[abc]` 大小写敏感、`[^\w]`、`[^\w]+`、`^.\\.$` 回溯长度 8	证明头文件与静态库链接后行为与上游一致
反直觉语义	空模式在 0 处长度 0、`.?` 空串 -1、`abc[` 编译 NULL 后 `re_match` 返回 -1、`ab\` 长度 2、40 个 `a` 只在 29 处停下	一旦有人"顺手修正"上游，这五条立刻红
单例语义	两次 `re_compile` 返回同一指针	把"不能跨线程共用"这件事变成可执行断言

CHECK 用宏而不是函数，是为了让失败行号直接指向断言所在行：

#define CHECK(cond) do {                                           \
    g_checks++;                                                    \
    if (!(cond)) {                                                 \
        g_failures++;                                              \
        fprintf(stderr, "FAIL %s:%d: %s\n", __FILE__, __LINE__, #cond); \
    }                                                              \
} while (0)

test_package/conanfile.py 沿用仓内最新约定：CMakeDeps + CMakeToolchain + cmake_layout，
test() 里直接 cmake.test(cli_args=["--output-on-failure"])，不做 cross_building 跳过 ——
CI 用 qemu 执行 aarch64 产物，跳过就等于没测。

MANIFEST.yml 里 upstream_test_in_build: false 的原因也写清楚了：上游 make test 需要
宿主可执行 + python3 才能跑完（tests/test1.c、tests/test2.c 是性能冒烟，
scripts/regex_test.py 要与 Python re 模块随机对拍 1000 条串），交叉编译阶段根本执行不了。

六、Demo：把"看不见的适配"摊在屏幕上

适配成果对读者来说通常只有一句"编译通过了"。这个库又特别抽象 —— 它没有音频、没有图像，
只有一个 int 返回值。所以在 Demo 工程里做了按钮 ⑨ → pages/TinyRegexDemo，
把 re_compile 的中间产物直接摊出来：

模式输入  →  记号表（逐个显示 tokenText）  →  匹配结果（下标 + 长度 + 高亮切片）

页面结构：

区块	内容	对应的 C 行为
4 个预设	`\d+` / `[a-z]+` / `^.\\.$` / `[^\w]+`	全部取自 `test_package/test.c` 的真实向量，点一下就能对照断言
模式 / 文本输入	即时重算	`re_compile` + `re_matchp` 两步
结果区	“命中：下标 X，长度 Y” / “未匹配：re_matchp 返回 -1” / “编译失败：re_compile 返回 NULL”	三种返回值的口语化映射
高亮区	前 / 命中 / 后三段着色	`int* matchlength` 的语义可视化
记号表	`#0 BEGIN`、`#1 DIGIT`、`#2 PLUS`、`#3 UNUSED`…	`re_compiled[]` 数组，含 UNUSED 哨兵
语义演示	「试 `".?" + 空串`」「试 40 个 a」	两条最容易误解的上游语义，一键复现

为什么在 ArkTS 里再写一遍引擎

设备侧跑的当然是 libtinyregexc.a 里的 re.c；但 re_match 只返回一个下标，
页面要展示"模式编译成了什么"就无从下手。于是把 re.c 逐行复刻到
entry/src/main/ets/utils/tre_bridge.ets（约 450 行），原则是只复刻行为、不修正上游：

/** 编译结果：除了记号表，还带上「是否发生静默截断」——C 侧没有这个信息，是复刻时补的 */
export class CompileResult {
  tokens: ReToken[] | null = null;
  truncated: boolean = false;
}

truncated 是唯一"多出来"的字段。C 侧遇到超长模式是静默截断，调用方永远不知道
自己少匹配了几个字符；页面需要把这件事提示出来，所以让编译函数额外回传一个标志位。
判断条件也照抄 C：

// 循环因记号数到顶退出、但模式还没吃完 → 发生了静默截断
out.truncated = i < pattern.length;

（一开始我用 pattern.length > 29 判断，\d+ 这种 3 字符 2 记号的模式会误报 ——
长度和记号数不是一回事。）

三层验证，同一套向量

层	位置	规模	跑在哪
C 消费者测试	`archives/t/tiny-regex-c/cci.20241025/test_package/test.c`	19 条 `CHECK`	CI（qemu 执行 aarch64）
ArkTS 逻辑断言	`entry/src/ohosTest/ets/test/TinyRegexBridge.test.ets`（已在 `List.test.ets` 注册）	17 个 `it`	真机 / 模拟器 ohosTest
本地快速对拍	tsc 编译后 Node 执行	30 条	开发机（秒级）

三层的向量是同一批：C 侧 19 条断言里能表达成"下标 + 长度"的，ArkTS 侧逐条复刻；
另外补了类内转义、[-a] 类首连字符、tokenText 渲染、sliceMatch 切片这几条
"页面要用到、但 C 测试没必要写"的断言。本地输出：

tiny-regex-c ArkTS port: 30 checks, 0 failures

MAX_REGEXP_OBJECTS 也在测试里钉死，任何"顺手把上限调到 100 让它更好用"的改动都会触发：

const compiled: CompileResult = compilePatternEx(fortyA);
expect(compiled.truncated).assertTrue();
expect((compiled.tokens as ReToken[]).length).assertEqual(MAX_TOKENS_KEPT + 1);  // 29 + 1
expect(matchPatternAt(compiled.tokens as ReToken[], fortyA).length).assertEqual(MAX_TOKENS_KEPT);
expect(MAX_REGEXP_OBJECTS).assertEqual(30);

七、开发环境：DevEco Studio 26 上的完整开发链路

本项目从三方库配方到 Demo 页面，全部在 DevEco Studio 26 上完成。这一节把「环境怎么配、每一步在哪跑、产物落在哪」摊开，方便照着复现。

7.1 环境清单

组件	版本 / 位置	用途
DevEco Studio	26（Windows 11 宿主）	IDE、SDK 管理、hvigor 构建
HarmonyOS SDK	`sdk/default/openharmony/native/sysroot`	交叉编译 sysroot、头文件
目标三元组	`aarch64-linux-ohos`	鸿蒙 PC / 设备侧产物
clang	DevEco 自带 NDK 工具链	编 `re.c`、手工验证交叉参数
hvigor	`DevEco Studio/tools/hvigor/bin/hvigorw.js`	构建 HAP（项目根无 `hvigorw` 时用它）
Conan	2.x	跑 `conan create`、test_package

开发界面如下：
在这里插入图片描述

7.2 三条链路，各跑在哪

配方链路：conan create archives/t/tiny-regex-c/cci.20241025 --build=missing，编译器路径取自 tools.build:compiler_executables['c']，指向 DevEco 26 自带的 clang，--target / --sysroot 都从 SDK 目录推导。
Demo 链路：在 DevEco Studio 26 里打开工程，用 IDE 自带的 hvigor 构建主 HAP 与测试 HAP；Windows 下项目根没有 hvigorw，所以命令行直接调 hvigorw.js。
验证链路：C 侧 19 条 CHECK 在 CI 用 qemu 跑；ArkTS 侧 17 个 it 在真机 / 模拟器 ohosTest 跑；本地 Node 对拍 30 条秒级出结果。

7.3 DevEco 26 上踩到的两个小坑

SDK 路径带空格。DevEco Studio 目录名里有空格，--sysroot= 必须整体加引号，否则 clang 会把路径截断成 …/DevEco，报「找不到 stdio.h」——看起来像 SDK 没装，实际是引号问题。
hvigor 版本与 IDE 绑定。DevEco 26 的 hvigor 不再随工程分发，命令行构建要显式指向 IDE 目录下的 hvigorw.js；用旧工程里的 hvigorw 会因版本不匹配报 Unknown task。

这两条都不影响产物正确性，但会让「第一次跑」多花半小时，记在这里省得重复踩。

八、复现命令

# 1) 构建并跑 test_package（aarch64 产物，CI 里用 qemu 执行）
conan create archives/t/tiny-regex-c/cci.20241025 --build=missing

# 2) 手工验证交叉编译参数（不依赖 conan，排除"配方写错"的可能）
clang --target=aarch64-linux-ohos \
      --sysroot=<DevEco>/sdk/default/openharmony/native/sysroot \
      -std=c99 -Wall -Wextra -O3 -fPIC \
      -I <src> -c re.c -o re.o
# exit=0，re.o 8744 字节，零告警

# 3) Demo 侧（Windows 11 + DevEco Studio 26，项目根无 hvigorw，用 DevEco 自带的）
node "…/DevEco Studio/tools/hvigor/bin/hvigorw.js" --mode module \
     -p product=default assembleHap            # 主 HAP
node "…/DevEco Studio/tools/hvigor/bin/hvigorw.js" --mode module \
     -p module=entry@ohosTest -p product=default assembleHap   # 测试 HAP

运行效果如下：
在这里插入图片描述
试验空串：

压力测试：

九、可复用的经验清单

先看 all 目标和 install 规则，再决定要不要 make。没有库目标就绕开 make 直接编；
不要用 make 的"成功退出码"当产出正确的证据。
上游无 tag 时，用完整 commit + cci.<commit 日期>，并把约定写进 source.note；
源地址千万别用 refs/heads/master。
反直觉语义一律原样保留，并把它写成断言。断言红 = 有人改了上游源码，这是设计，不是回归。
C 里 do { } while (*p++) 的扫描循环，移植前数清每轮自增几次。类内转义吃两字符就是
这条的实例。
给"隐式状态"加显式回传。C 的静默截断没有返回值可用，复刻时补一个 truncated 标志，
页面才有话可说 —— 但判断条件必须照抄 C，别自己发明。
三层验证用同一批向量：C 消费者测试 → ArkTS 逻辑测试 → 本地 Node 对拍。
三层都过，才能说"页面显示的数 = 设备侧 C 库给的值"。

十、附：最大子数组的分治解法（O(n log n)）

线性版是 O(n)，但面试里常被追问「能不能用分治做」。分治的思路很干净：最大子数组要么完全落在左半，要么完全落在右半，要么跨过中点。前两种递归，第三种单独算——而第三种恰好可以拆成「左半的 suffix 最大和」+「右半的 prefix 最大和」。

public int maxSubArrayDivide(int[] nums) {
    return solve(nums, 0, nums.length - 1);
}

private int solve(int[] a, int lo, int hi) {
    if (lo == hi) return a[lo];                 // 单元素：非空，直接返回它本身

    int mid = lo + (hi - lo) / 2;
    int leftMax  = solve(a, lo, mid);           // 完全在左半
    int rightMax = solve(a, mid + 1, hi);       // 完全在右半
    int crossMax = crossSum(a, lo, mid, hi);    // 跨中点

    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

/** 跨中点最大和 = 左半以 mid 结尾的最大 suffix + 右半以 mid+1 开头的最大 prefix */
private int crossSum(int[] a, int lo, int mid, int hi) {
    int sum = 0, leftSuffix = Integer.MIN_VALUE;
    for (int i = mid; i >= lo; i--) {           // 从 mid 往左累加
        sum += a[i];
        leftSuffix = Math.max(leftSuffix, sum);
    }

    sum = 0;
    int rightPrefix = Integer.MIN_VALUE;
    for (int i = mid + 1; i <= hi; i++) {       // 从 mid+1 往右累加
        sum += a[i];
        rightPrefix = Math.max(rightPrefix, sum);
    }

    return leftSuffix + rightPrefix;
}

几个容易写错的点：

细节	正确做法	写错的后果
递归基	`lo == hi` 直接返回 `a[lo]`	返回 0 就退化成「允许空子数组」，全负数组又错
`leftSuffix` / `rightPrefix` 初值	`Integer.MIN_VALUE`	取 0 会让「跨中点」这一支永远 ≥ 0，全负时压过真实答案
跨中点两侧都必须非空	左半至少含 `mid`，右半至少含 `mid+1`	允许一侧为空，等价于把「跨中点」退化成「只在一侧」，与递归分支重复且可能取到空数组
中点计算	`lo + (hi - lo) / 2`	`(lo + hi) / 2` 在超大数组上可能溢出

对撞验证

分治版和线性版用同一套穷举空间对撞：长度 1～6、值域 [-2,2] 的全部序列，共 19530 条；再加随机 5 万组（长度 1～200，值域 [-100,100]）。

穷举 19530 条：分治 vs 线性 结果不一致=0
随机 50000 组：分治 vs 线性 结果不一致=0
全负数组 [-3,-1,-2]：分治=-1  线性=-1  暴力=-1
单元素 [-2]：分治=-2  线性=-2  暴力=-2

结果完全一致，零失败。 这也顺带验证了上面那张表里的每一条——只要有一处写错，全负集合（126 条）立刻会暴露出来，和第五节里「反直觉语义」那组断言的失败面一模一样。

需要说明的是：分治是 O(n log n)，在这题上不是更优解，它的价值在于「换一种思路验证答案」——当两种复杂度不同的实现给出完全相同的输出时，你对正确性的信心才真正建立起来。

分治递归树示意

下面这张图把 solve(a, lo, hi) 的递归展开画出来：每个节点是一次 solve 调用，叶子是单元素区间，跨中点的 crossSum 在每层合并时各算一次。

从图里能直接读出复杂度：树高 log n，每层所有 crossSum 加起来扫描的区间总长是 n，所以总代价 O(n log n)；递归栈深度 log n，额外空间 O(log n)。

三种解法横向对比

解法	时间复杂度	空间复杂度	是否允许空子数组	适用场景
暴力枚举	`O(n²)`	`O(1)`	否	对拍基准，`n ≤ 200` 时够用
分治	`O(n log n)`	`O(log n)`（递归栈）	否（递归基返回 `a[lo]`）	面试追问、并行化改造
线性 DP（Kadane）	`O(n)`	`O(1)`	否（`cur = max(a[i], cur + a[i])`）	生产环境首选

三者的关系可以这样理解：分治把「跨中点」这一支拆成两个方向的前缀/后缀扫描，而线性 DP 正是把「以 i 结尾的最大和」这个状态一路滚动下去——分治的 crossSum 是线性 DP 的一次性版本，线性 DP 是分治把递归摊平后的结果。

分治的并行化潜力

分治在这题上不是最优解，但它有一个线性 DP 没有的性质：左右两半的递归调用彼此独立，可以直接丢进线程池并行。伪代码：

private int solveParallel(int[] a, int lo, int hi) {
    if (hi - lo < THRESHOLD) return solve(a, lo, hi);   // 小区间退化为串行，避免任务调度开销

    int mid = lo + (hi - lo) / 2;
    Future<Integer> left  = pool.submit(() -> solveParallel(a, lo, mid));
    Future<Integer> right = pool.submit(() -> solveParallel(a, mid + 1, hi));
    int crossMax = crossSum(a, lo, mid, hi);            // 跨中点必须等两半都算完才能合并

    return Math.max(Math.max(left.get(), right.get()), crossMax);
}