连续子数组最大和
经典的动态规划题，貌似直接暴力速度更快一点？
剑指 Offer 42. 连续子数组的最大和
难度简单353收藏分享切换为英文接收动态反馈
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
下面给出两种解法：动态规划和暴力
// 连续子数组最大和
// 以nums[i]结尾的连续子数组最大和
// 上一个结尾最大值有没大于0，大于0就算在当前的最大值，不大于零就以当前的值重算
function dp_solution(nums: number[]) {
let dp = Array.from(nums);
for (let i = 1; i < dp.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
}
return Math.max(...dp);
}
function solution(nums: number[]){
if(!nums.length) return 0
// 维护一个最大值
let sumValue = nums[0];
let maxValue = sumValue;
for (let i=1; i<nums.length; i++) {
if(sumValue>0){
// 累加和比0大的时候继续累加
sumValue += nums[i];
}else{
// 累加和小于0，丢弃，从当前重新开始计算
sumValue = nums[i];
}
// 当前累加和大于最大值时更新最大值
maxValue = Math.max(maxValue,sumValue);
}
return maxValue;
}
const nums: number[] = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
const r = solution(nums)
console.log(r); // 6
dp数组还可以优化，因为只用到上一个值和当前值，只需要两个变量，空间复杂度优化到了常数阶。
// 改进后的动态规划解法
function dp_solution(nums: number[]) {
let last = nums[0], now = 0, maxValue = last;
for (let i = 1; i < nums.length; i++) {
now = Math.max(last + nums[i], nums[i]);
maxValue = Math.max(maxValue,now);
last = now;
}
return maxValue;
}
貌似暴力法更快一点。。
