Open xszi opened 3 years ago
数学归纳法
第一步:定义子问题
动态规划是将整个数组归纳考虑,假设我们已经知道了以第 i-1
个数结尾的连续子数组的最大和 dp[i-1]
,显然以第i个数结尾的连续子数组的最大和的可能取值要么为 dp[i-1]+nums[i]
,要么就是 nums[i] 单独成一组,也就是 nums[i]
,在这两个数中我们取最大值
第二步:实现需要反复执行解决的子子问题部分
dp[n] = Math.max(dp[n−1]+nums[n], nums[n])
第三步:识别并求解出边界条件
dp[0]=nums[0]
最后,翻译成代码求解
const largestChildSum = (nums) => {
let dp = new Array();
dp[0] = nums[0];
let max = nums[0];
for (let i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i- 1] + nums[i], nums[i]);
if (max < dp[i]) {
max = dp[i];
}
}
return max;
}
复杂度分析:
时间复杂度:O(n) 空间复杂度:O(n)
简化空间复杂度:
const largestChildSum = (nums) => {
let max = nums[0], pre = 0
for(const num of nums) {
if(pre > 0) {
pre += num
} else {
pre = num
}
max = Math.max(max, pre)
}
return max
}
空间复杂度:O(1)
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
进阶:
如果你已经实现复杂度为
O(n)
的解法,尝试使用更为精妙的分治法求解。leetcode