# 连续子数组的最大和|博客系列

> 本文详细讲解了如何用O(n)时间复杂度解决连续子数组最大和问题（最大子段和/Kadane算法），包括题目描述、解题思路、JavaScript代码实现及测试示例，适合前端和算法学习者参考。

- 原文：https://feinterview.poetries.top/docs/fe-blog-docs/blog-docs/data-struct/34-%E8%BF%9E%E7%BB%AD%E5%AD%90%E6%95%B0%E7%BB%84%E7%9A%84%E6%9C%80%E5%A4%A7%E5%92%8C
- 来源：前端进阶之旅（feinterview.poetries.top）
- 更新：2025.10.25

---

### 题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，要求时间复杂度为`O(n)`

例如:`[6,-3,-2,7,-15,1,2,2]`,连续子向量的最大和为8(从第0个开始,到第3个为止)。

### 解题思路

解题方法有很多种,但这里要求时间负责度为`O(n)`,那也是要求要在一个`for`循环中搞定.

1. 定义一个连续子数组的最大值`max`;
2. 定义一个连续子数组的和`sum`;
3. 前两个定义的默认值都是数组第一项, 然后从第二项开始累加;
4. 判断每次累加的和`sum`是否大于`0`,若是大于`0`才对后面的累加有贡献,若小于`0`则`sum`从当前值开始重新开始;
5. 比较每次循环的`max`和`sum`的大小,取大的.

### coding

```javascript
function findGreatestSumOfSubArray(array) {
    if (array && array.length > 0) {
        let sum = array[0],
            max = array[0];
        for (let i = 1; i < array.length; i++) {
            if (sum < 0) {
                sum = array[i];
            } else {
                sum += array[i];
            }
            if (sum > max) max = sum;
        }
        return max;
    }
    return 0;
}
```

**测试代码**

```javascript
console.log(findGreatestSumOfSubArray([-2, 6, 7, 8, -3, 4, -6]))
// 22 (6+7+8)
```
