# 最大子数组
# 难度：简单
# 描述：
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
# 样例：
给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为 6
# 思路分析：
本题只要找出最大和即可，保存两个值，一个为元素之间相加的值(需比较元素相加的值与当前元素的大小)，一个为最大值。
# 代码：
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
const maxSubArray = function(nums) {
let max = nums[0]; // 初始化最大值
let newMax = nums[0]; // 数组元素相加的缓存值
for (let i = 1; i < nums.length; i++) {
newMax = Math.max(newMax + nums[i], nums[i]); // 相加是否大于当前值
max = Math.max(newMax, max); // 与最大值相比
}
return max;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
第二种方法更难理解点，可以扩展一下思路：
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
const maxSubArray = function(nums) {
var nSum = nums[0]; // 数组元素相加的缓存值
var nMax = nSum; // 初始化最大值
for (var i = 1; i < nums.length; i++) {
var curNum = nums[i]; // 当前元素
if (curNum >= 0) nSum = nSum > 0 ? nSum + curNum : curNum;
// 如果两个值都大于0 两个值相加。否则就取后一个大于0的
else nSum = nSum < curNum ? curNum : nSum + curNum; // 如果新加的值小于0 判断结果是否大于新加的值 小于的话就改为新加的值
nMax = Math.max(nMax, nSum); // 最大值与数组元素相加值比较
}
return nMax;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 最大和的数组：
如果你想把最大和的数组都找出来，你需要保存数组的开始下标和结束下标，这里我演示了第一个方法，下面那个方法也是一样：
const maxSubArray = function(nums) {
let max = {
num: nums[0],
start: 0,
end: 1 // 结束的下标 后面要切割数组 需比当前下标+1.把当前值也切割
};
let newMax = {
num: nums[0],
start: 0,
end: 1
};
for (let i = 1; i < nums.length; i++) {
if (newMax.num + nums[i] > nums[i]) {
// 相加大于当前值 缓存改值和结束下标
newMax.num = newMax.num + nums[i];
newMax.end = i + 1;
} else {
// 小于当前值 重置start end
newMax.num = nums[i];
newMax.start = i;
newMax.end = i + 1;
}
// 最大值被超过 把值赋给最大值
if (max.num < newMax.num) {
max.num = newMax.num;
max.start = newMax.start;
max.end = newMax.end;
}
}
let arr = nums.slice(max.start, max.end); // 找出最大和的子数组
return max.num; // 子数组的最大和
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32