综合文章

# 题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，要求时间复杂度为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

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;
}

测试代码

console.log(findGreatestSumOfSubArray([-2, 6, 7, 8, -3, 4, -6]))
// 22 (6+7+8)
阅读全文

← 中序遍历 →