算法:找到一个具有最大和的连续子数组
原创
2019-9-11
09:27
编辑于
2020-4-6
11:18
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
function maxSubArray(arr) {
var max = arr[0], sum = arr[0], start = 0, end = 0, lastStart = 0
for (var i = 1; i < arr.length; i++) {
if (sum < 0) {
sum = arr[i]
start = i
} else {
sum = arr[i] + sum
}
if (sum > max) {
lastStart = start
end = i
max = sum
}
}
if (start > end) {
start = lastStart
}
return [max, JSON.stringify(arr.slice(start, end + 1))]
}
console.log(maxSubArray([10, -5, -6, 2, 3, 1])) // [10, "[10]"]
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) // [6, "[4,-1,2,1]"]
console.log(maxSubArray([2, 10, -5, -11, 1, 2, -100, 100])) // [100, "[100]"]
关注我的公众号