京公网安备11010502063487号给定一个整数数组（至少一个元素），找出和最大的连续子数组，返回这个最大和。暴力枚举所有子数组是 O(n²)（用累加求和避免第三层循环）。Kadane 算法只扫描一遍：维护"以当前元素结尾的最大子数组和" cur，遇到下一个元素 x 时，要么把它接在前面那段后面（cur + x），要么从它自己重新开始（x），取更大的。全局最大值 best 是所有 cur 里最大的。本文用真实数据展示"把最大和初始化为 0"的错误，验证 Kadane 与分治法答案一致并比较耗时，给出五种语言的实现，并把每一步的取舍做成分步演示。
完整题目见官方页面（链接在文末）。子数组必须非空，并且是连续的。基准解枚举所有起点和终点，用累加求和，O(n²)。一共 14 组用例，覆盖：官方示例、单个元素、全是负数、全是 0、全是正数、需要跨过负数才能拿到更大和的数组：
输入 [[-2,1,-3,4,-1,2,1,-5,4]] 输出 6 输入 [[1]] 输出 1 输入 [[5,4,-1,7,8]] 输出 23 输入 [[-1]] 输出 -1 输入 [[-3,-2,-1]] 输出 -1 输入 [[-1,-2]] 输出 -1
如果把最大和的初始值写成 0，对含有正数的数组没有影响，但当数组全是负数时，答案应该是其中最大的那个负数（子数组必须非空），而写成 0 的版本会返回 0，等于允许选一个空的子数组。下面是真实运行结果：
# 最大和初始化为 0 的写法 [-1]: 初始化为 0 -> 0 solve -> -1 [-3, -2, -1]: 初始化为 0 -> 0 solve -> -1 [-2, 1, -3, 4, -1, 2, 1, -5, 4]: 初始化为 0 -> 6 solve -> 6 [-1, -2]: 初始化为 0 -> 0 solve -> -1
[-1] 应该是 -1，初始化为 0 的写法返回 0；[-3, -2, -1] 应该是 -1，写法返回 0；有正数的官方示例两种写法一致，都是 6。所以初始值应该取 nums[0]。
cur 和 best 都从 nums[0] 开始。对每个后续元素 x：cur = max(x, cur + x)，含义是"以 x 结尾的最大和"，如果前面那段的和为负（是负担），就丢掉它从 x 重新开始；然后 best = max(best, cur)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums): best = cur = nums[0] # 数组至少有一个元素；以第 0 个元素结尾的最大子数组和就是它自己 for x in nums[1:]: cur = max(x, cur + x) # 以 x 结尾的最大和：要么接在前面那段后面，要么从 x 重新开始 best = max(best, cur) return best
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[-2,1,-3,4,-1,2,1,-5,4]] → 6 [[1]] → 1 [[5,4,-1,7,8]] → 23 [[-1]] → -1 [[-3,-2,-1]] → -1 [[-1,-2]] → -1
Java · 解法代码class Solution { public int maxSubArray(int[] nums) { int best = nums[0], cur = nums[0]; // 数组至少有一个元素 for (int i = 1; i < nums.length; i++) { cur = Math.max(nums[i], cur + nums[i]); // 以 nums[i] 结尾的最大和：接在前面那段后面，或者从自己重新开始 best = Math.max(best, cur); } return best; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[-2,1,-3,4,-1,2,1,-5,4]] → 6 [[1]] → 1 [[5,4,-1,7,8]] → 23 [[-1]] → -1 [[-3,-2,-1]] → -1 [[-1,-2]] → -1
Go · 解法代码func maxSubArray(nums []int) int { best, cur := nums[0], nums[0] // 数组至少有一个元素 for _, x := range nums[1:] { if cur+x > x { // 以 x 结尾的最大和：接在前面那段后面，或者从 x 重新开始 cur += x } else { cur = x } if cur > best { best = cur } } return best }
$ go build -o bin . && ./bin < cases.jsonl [[-2,1,-3,4,-1,2,1,-5,4]] → 6 [[1]] → 1 [[5,4,-1,7,8]] → 23 [[-1]] → -1 [[-3,-2,-1]] → -1 [[-1,-2]] → -1
JavaScript · 解法代码function maxSubArray(nums) { let best = nums[0], cur = nums[0]; // 数组至少有一个元素 for (let i = 1; i < nums.length; i++) { cur = Math.max(nums[i], cur + nums[i]); // 以 nums[i] 结尾的最大和：接在前面那段后面，或者从自己重新开始 best = Math.max(best, cur); } return best; }
$ node run.js < cases.jsonl [[-2,1,-3,4,-1,2,1,-5,4]] → 6 [[1]] → 1 [[5,4,-1,7,8]] → 23 [[-1]] → -1 [[-3,-2,-1]] → -1 [[-1,-2]] → -1
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: int maxSubArray(vector<int>& nums) { int best = nums[0], cur = nums[0]; // 数组至少有一个元素 for (size_t i = 1; i < nums.size(); i++) { cur = max(nums[i], cur + nums[i]); // 以 nums[i] 结尾的最大和：接在前面那段后面，或者从自己重新开始 best = max(best, cur); } return best; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[-2,1,-3,4,-1,2,1,-5,4]] → 6 [[1]] → 1 [[5,4,-1,7,8]] → 23 [[-1]] → -1 [[-3,-2,-1]] → -1 [[-1,-2]] → -1
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
分治的思路：最大子数组要么完全在左半，要么完全在右半，要么跨过中点；跨过中点的那种，等于"以中点结尾往左延伸的最大和"加上"以中点右边一个开始往右延伸的最大和"。时间 O(n log n)。我在 Python 里实现了分治，验证 Kadane、分治、暴力三种做法在 20000 个随机数组上答案完全一致，并比较了耗时：
随机 20000 个数组：Kadane / 分治 / 暴力三种做法答案全部一致：True 长度 n 的随机数组上的耗时（三次中最快）： n= 10000: Kadane 0.71 ms 分治 9.50 ms n= 100000: Kadane 6.80 ms 分治 113.74 ms n= 500000: Kadane 33.66 ms 分治 640.26 ms
三种做法答案一致。分治比 Kadane 慢很多：n = 50 万时 640.3ms 对 33.7ms，约 19 倍，主要是因为分治要多做 log n 倍的工作，并且有递归调用的开销。
每个规模取三次中最快的一次：
数组长度 n | 暴力解 | 本文解法
1000 | 22.313 ms | 0.060 ms
3000 | 202.542 ms | 0.169 ms
10000 | 2429.590 ms | 0.576 ms
1000000 | （未测，太慢） | 58.761 ms暴力解从 1000 到 3000（3 倍）增长约 9.1 倍，从 3000 到 1 万增长约 12 倍，符合平方；Kadane 从 1000 到 1 万（10 倍）增长约 9.6 倍，是线性，100 万个元素只需要 58.8ms。n = 1 万时暴力 2430ms，Kadane 0.58ms，约 4200 倍。暴力解在 n = 100 万时没有再测。
Python 版本另外和暴力解做了随机对拍，数组长度 1 到 15、取值 -10 到 10，包括全是负数的数组：
随机对拍 20000 组（长度 1 到 15、取值 -10 到 10 的随机数组（包括全是负数的数组）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [-2, 1, -3, 4, -1, 2, 1, -5, 4]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。观察：遇到 1 时，前面的 -2 是负担，丢掉，从 1 重新开始；遇到 4 时，前面的 -2（= 1 + -3）又是负担，从 4 重新开始；之后 4、-1、2、1 一路接下去，和达到 6，这就是最大的子数组 [4, -1, 2, 1]。