本文是我在学习 LeetCode-最大子序和 多解法时偶然发现的哈
由于我只是小小前端开发,日常工作跟算法相关的也不多,表达不当或理解不对的地方,感谢您点评指正~
本文解一到解四,是一个递进和推导的过程。
场景
给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
解一:暴力法 O(n^3)
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let maxSum = -Infinity;
for (let i = 0; i < nums.length; i++) {
for (let j = i; j < nums.length; j++) {
let sum = -Infinity;
for (let t = i; i <= j; t++) {
sum += t;
}
if (maxSum < sum) {
maxSum = sum;
}
}
}
return maxSum;
};
这种超出时间限制
解二: 优化暴力法 O(n^2)
去掉 t 的遍历,对 sum 计算的优化
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let maxSum = -Infinity;
for (let i = 0; i < nums.length; i++) {
let sum = 0;
for (let j = i; j < nums.length; j++) {
sum += nums[j];
if (maxSum < sum) {
maxSum = sum;
}
}
}
return maxSum;
};
解三:动态规划 T(n) = O(n) S(n) = O(n)
- 动态规划其实是对解二的优化, 去掉 j 的迭代
- 上面的每个 i 的迭代,是以 i 为起点(含 i),j 为终点求 sum
- 假设 DP[i] 表示以 i 为起点(含 i)到终点的连续子序列的最大和
- DP 递推公式
DP[i] = Math.max(nums[i], nums[i] + DP[i+1])
- 由于 DP[i+1] 是先得到的,需要从后往前计算。反过来
- 假设 DP[i] 表示从第一个元素开始到 i (含 i)中连续子序列的最大和
- DP 递推公式
DP[i] = Math.max(nums[i], nums[i] + DP[i-1])
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let maxSum = -Infinity;
const DP = Array(nums.length);
for (let i = 0; i < nums.length; i++) {
if (i === 0) {
DP[0] = maxSum = nums[0];
continue;
}
DP[i] = Math.max(nums[i], nums[i] + DP[i-1])
if (maxSum < DP[i]) {
maxSum = DP[i];
}
}
return maxSum;
};
解四:Kadane算法 T(n) = O(n) S(n) = O(1)
在解三动态规划中,for 循环只用到 DP[i] DP[i-1], 并不需要用整个 Array(nums.length),用一个变量 DP_i 即可
var maxSubArray = function(nums) {
let maxSum = -Infinity;
let DP_i;
for (let i = 0; i < nums.length; i++) {
if (i === 0) {
DP_i = maxSum = nums[0];
continue;
}
DP_i = Math.max(nums[i], nums[i] + DP_i);
if (maxSum < DP_i) {
maxSum = DP_i;
}
}
return maxSum;
};
DP_i 表示以从第一个元素开始到 i (含 i)中连续子序列的最大和,如代码所示,优化后的公式为
DP_i = Math.max(nums[i], nums[i] + DP_i);
其实这就是著名的 Kadane算法, 参见 维基百科 - 最大子数列问题