剑指offer JZ30 - 连续子数组最大和- JavaScript

92 阅读 0 评论 61 点赞

我是靠谱客的博主善良春天，这篇文章主要介绍剑指offer JZ30 - 连续子数组最大和- JavaScript，现在分享给大家，希望可以做个参考。

1、题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

例如：输入 [-2,1,-3,4,-1,2,1,-5,4] ，输出 6。解释：连续子数组 [4,-1,2,1] 的和最大为 6。

2、解题思路

1.初始化当前最大连续子序列和为 sum，结果为 result，result 取数组的第一个元素
2.如果 sum>0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数组
3.如果 sum<0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
4.每次比较 sum 和 result 的大小，将最大值置为 result，遍历结束返回结果

var maxSubArray = function(array) {
var sum = 0;
var result = array[0]; // 初始化 result 为数组的第一个元素
for(var i=0;i<array.length;i++){
if(sum > 0){
sum += array[i];
}else{
sum = array[i];
}
result = Math.max(result, sum);
}
return result;
};