前言

今天是重新补 C 语言基础的第三天。

前一天完成了二分查找和有序数组原地去重，但 01_array_tools.c 里还有一个函数没有完成：MaxSubarraySum。今天的目标很集中，就是独立写出最大连续子数组和，跑过混合数组和全负数组测试，再把时间复杂度、空间复杂度以及嵌入式中的实际意义讲清楚。

最后的关键运行结果是：

Building 01_array_tools.c
Running 01_array_tools.exe
01_array_tools passed

完整脚本最后仍显示 2 exercise(s) failed，但失败的是后面的 02_ring_buffer.c 和 03_uart_frame_parser.c。它们分别属于 Day 4 和 Day 5，不是今天的任务。

一、题目是什么

给定一个整数数组，需要找到和最大的连续子数组，并返回这个最大和。

例如：

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

其中和最大的连续区间是：

[4, -1, 2, 1]

结果为：

4 + (-1) + 2 + 1 = 6

题目的重点不只是求和，还要求子数组中的元素在原数组里连续。

二、从暴力思路到一次遍历

最直接的做法是枚举每个起点和终点，然后计算区间和。如果每次又重新求和，时间复杂度会达到 O(n³)；即使在枚举过程中累加，通常也需要 O(n²)。

今天采用的是 Kadane 算法，只遍历数组一次。

核心问题是：遍历到当前元素时，前面的连续区间还值不值得保留？

如果前面的累计和小于 0，它加到当前元素上只会拖累结果，因此应该从当前元素重新开始。如果前面的累计和不小于 0，它仍然有正向贡献，就继续累加。

代码如下：

static int MaxSubarraySum(const int *arr, size_t len)
{
    int max_sum = arr[0];
    int current_sum = arr[0];

    for (size_t i = 1; i < len; i++) {
        if (current_sum < 0) {
            current_sum = arr[i];
        } else {
            current_sum += arr[i];
        }

        if (current_sum > max_sum) {
            max_sum = current_sum;
        }
    }

    return max_sum;
}

这里有两个状态：

• current_sum：以当前元素结尾的最大连续和。
• max_sum：目前为止见过的最大连续和。

这两个变量不能混在一起。current_sum 负责判断当前连续区间是否继续，max_sum 负责保存全局最优结果。

三、为什么不能初始化为 0

今天测试里还有一个全负数组：

int all_negative[] = {-8, -3, -6, -2, -5};

正确答案是 -2，因为最大连续子数组可以只包含一个元素。

如果把 current_sum 和 max_sum 初始化为 0，算法最后可能返回 0。但 0 根本不在数组里，这相当于错误地允许选择空数组。

因此我的实现使用第一个元素初始化：

int max_sum = arr[0];
int current_sum = arr[0];

然后从下标 1 开始遍历。这样即使数组中全是负数，也会保留其中最大的那个负数。

这个边界让我再次意识到，算法能通过常规样例不代表实现正确。混合正负数、全负数和单元素数组都应该单独考虑。

四、复杂度分析

这次实现只遍历数组一次：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

常见复杂度可以这样理解：

复杂度	常见场景
O(1)	寄存器置位、数组按下标访问
O(log n)	有序数组二分查找
O(n)	数组遍历、原地去重、最大连续子数组和
O(n log n)	归并排序、堆排序、平均情况下的快速排序
O(n²)	两层循环枚举数组元素对或区间

复杂度不是只在刷算法题时才有用。它反映了输入规模增大后，程序执行时间和内存使用会怎样增长。

五、为什么嵌入式也要关心复杂度

我使用的 STM32F103C8T6 主频为 72MHz，SRAM 只有 20KB。和桌面程序相比，嵌入式系统的 CPU、内存和实时期限都更紧张。

如果一个处理函数运行在高频任务中，O(n²) 和 O(n) 的差距可能直接影响任务能否按时完成。数据处理时间过长，可能造成 UART 接收不及时、采样数据丢失或者其他任务得不到调度。

空间复杂度同样重要。今天的算法只使用两个整数变量，不需要额外数组，也不需要动态分配内存。这种 O(1) 额外空间的实现更适合资源受限的 MCU。

当然，实际项目不能只看大 O 表示法，还要考虑：

1. 数组的实际最大长度。
2. 函数的调用频率。
3. 是否处于中断或高优先级任务的数据路径。
4. 整数累加是否可能溢出。
5. 输入指针和长度是否可信。

算法复杂度给出增长趋势，真实执行时间仍然需要结合硬件和使用场景测量。

六、今天的测试结果

运行完整练习脚本后，关键输出如下：

Building 01_array_tools.c
Running 01_array_tools.exe
01_array_tools passed
Building 02_ring_buffer.c
Running 02_ring_buffer.exe
FAIL ...02_ring_buffer.c:76 expression: RingBufferPush(&rb, (uint8_t)(0xA0 + i)) == 0
Building 03_uart_frame_parser.c
warning: 'CalcChecksum' defined but not used [-Wunused-function]
Running 03_uart_frame_parser.exe
FAIL ...03_uart_frame_parser.c:79 expression: ParseFirstFrame(valid, sizeof(valid), &frame, &used_len) == 1
2 exercise(s) failed

这次不能只看最后的失败数量。01_array_tools passed 已经说明 Day 3 的数组任务完整通过。剩余两个失败来自尚未完成的环形缓冲区和 UART 帧解析，应该在后续训练日分别处理。

七、今天的收获

今天主要记住了四点：

1. current_sum 表示以当前元素结尾的最大连续和。
2. 负的前缀和不会帮助后续区间，应该及时丢弃。
3. 用数组首元素初始化，才能正确处理全负数组。
4. 嵌入式也要关注时间和空间复杂度，因为 CPU、SRAM 和实时期限都有限。

总结

Day 3 的代码量不大，只新增了一个函数，但这个练习把状态定义、边界测试和复杂度分析连在了一起。

今天完成后，01_array_tools.c 中的二分查找、有序数组原地去重和最大连续子数组和都已经通过。下一步将进入环形缓冲区，重点理解空、满、回绕以及 UART 中断接收中的使用方式。