LintCode 41. 最大子数组 JavaScript算法
程序员文章站
2022-07-15 23:35:13
...
描述
给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。
说明
子数组最少包含一个数
样例
- 样例1:
输入:[−2,2,−3,4,−1,2,1,−5,3]
输出:6
解释:符合要求的子数组为[4,−1,2,1],其最大和为 6。
- 样例2:
输入:[1,2,3,4]
输出:10
解释:符合要求的子数组为[1,2,3,4],其最大和为 10。
挑战
要求时间复杂度为O(n)
解析
const maxSubArray = function (nums) {
if (nums === null || nums.length === 0) {
return 0;
}
var maxSum = nums[0], minSum = 0, sum = 0;
var i;
for (i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum - minSum > maxSum) {
maxSum = sum - minSum;
}
if (sum < minSum) {
minSum = sum;
}
}
return maxSum;
}
运行结果
上一篇: java如何将String转换为Int
下一篇: 和为S的连续正数序列