# 面试题16.17 连续数列
给定一个整数数组，找出总和最大的连续数列，并返回总和。
输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
1
2
3
2
3
# 思路
- 动态规划
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
const dp = new Array(nums.length)
dp[0] = nums[0]
dp[1] = Math.max(nums[0], nums[0]+nums[1],nums[1])
if(nums.length === 0) return 0;
if(nums.length === 1) return dp[0]
let res = dp[1]
if(nums.length === 2) return res
for (let i = 1, len = nums.length; i < len; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]) // 动态转移方程
res = Math.max(res,dp[i])
}
return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
- 遍历 分治
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
for(let i =1,len =nums.length;i<len;i++){
if(nums[i-1]>0){
nums[i] += nums[i-1]
}
}
return Math.max.apply(null,nums)
};
/*
一次遍历
维护一个累计的和 sum，每次遇到一个新的数，判断
- 如果新的数加上 sum 大于当前当前累加和，那么重置 sum = 0
- 否则 sum 加上这个数
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18