最大子数组和问题：第二种算法的效率提升原因及子数组右端移动机制解析

咱们先回顾下问题背景：我们要计算数组的最大连续子数组和，示例数组是{-1,2,4,-3,5,2,-5,2}。这里有两种实现算法，咱们来逐个解答你的疑问。

两种算法实现 #

第一种三重循环的算法：

int best = 0;
for (int a = 0; a < n; a++) {
    for (int b = a; b < n; b++) {
        int sum = 0;
        for (int k = a; k <= b; k++) {
            sum += array[k];
        }
        best = max(best,sum);
    }
}
cout << best << "\n";

第二种优化后的双重循环算法：

int best = 0;
for (int a = 0; a < n; a++) {
    int sum = 0;
    for (int b = a; b < n; b++) {
        sum += array[b];
        best = max(best,sum);
    }
}
cout << best << "\n";

1. 第二种算法效率提升的具体原因 #

第一种算法的核心问题是重复计算了大量子数组和，完全做了无用功：

• 当外层循环固定左端点a，中间循环移动右端点b时，第一种算法每次都要从a到b重新遍历求和（第三重循环）。比如a=1、b=2时计算了array[1]+array[2]，当b=3时又要重新算array[1]+array[2]+array[3]，前两个元素的求和完全是重复操作。
• 第二种算法则利用了累加复用的思想：固定左端点a后，初始化sum=0，右端点b每向右移动一位，只需要把当前array[b]加到之前的sum里，就能直接得到a到b的子数组和，彻底避免了重复计算。

从时间复杂度来看，第一种是O(n³)，第二种是O(n²)——当数组规模n较大时，后者的运行速度会比前者快得多（比如n=1000时，前者要执行1e9次操作，后者只需要1e6次）。

2. 第二种算法中子数组的右端是如何移动的 #

咱们结合代码逻辑一步步拆解：

• 外层循环的a是子数组的左端点，每一轮外层循环都会固定一个左端点（比如第一轮a=0，第二轮a=1，直到a=n-1）。
• 内层循环的b就是子数组的右端点，移动逻辑非常清晰：
  1. 每轮外层循环开始时，b从当前左端点a出发（也就是子数组一开始只有array[a]这一个元素）。
  2. 每次内层循环，b都会递增1（也就是右端点向右移动一位），把新的元素array[b]加入到当前的sum中，此时sum就代表从a到b的连续子数组的和。
  3. 每次更新sum后，都会和当前的best比较，保留最大的子数组和。

举个具体例子，当a=1时：

• b=1：子数组是[2]，sum=2
• b=2：右端点右移到2，子数组是[2,4]，sum=2+4=6
• b=3：右端点再右移到3，子数组是[2,4,-3]，sum=6+(-3)=3
• 以此类推，直到b遍历到数组末尾，完成左端点为1的所有连续子数组的计算。

内容的提问来源于stack exchange，提问作者ProgrammerGuy