知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 07 - 最大子数组和 ## 题目(LeetCode 53) 给定一个整数数组,找到一个具有最大和的连续子数组,返回其最大和。 ## 解法:Kadane 算法 ```java class Solution { public int maxSubArray(int[] nums) { int cur = nums[0], max = nums[0]; for (int i = 1; i < nums.length; i++) { cur = Math.max(nums[i], cur + nums[i]); // 要么重新开始,要么接上 max = Math.max(max, cur); } return max; } } ``` > 💬 **Q:有其他解法吗,可以用 DP 吗?** > > Kadane 算法本质上就是 DP 的空间优化版。 > > DP 定义:`dp[i]` = 以 `nums[i]` 结尾的最大子数组和 > 转移方程:`dp[i] = max(nums[i], dp[i-1] + nums[i])` > 答案:`max(dp[0..n-1])` > > Kadane 里的 `cur` 就是 `dp[i]`,用一个变量滚动代替了整个数组。 > > ```java > // DP 显式数组版 > public int maxSubArray(int[] nums) { > int[] dp = new int[nums.length]; > dp[0] = nums[0]; > int max = dp[0]; > for (int i = 1; i < nums.length; i++) { > dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); > max = Math.max(max, dp[i]); > } > return max; > } > ``` > > 三种解法对比: > - Kadane(DP 空间优化):O(n) 时间,O(1) 空间,面试首选 > - DP 显式数组:O(n) 时间,O(n) 空间,更容易理解转移方程 > - 分治(见下方解法二):O(n log n) 时间,O(log n) 空间,面试追问时用 ## 复杂度 - 时间 O(n),空间 O(1) ## 一句话总结 当前和为负就丢掉重新开始,一直维护全局最大值。 ## 解法二:分治 将数组分成左右两半,最大子数组要么在左半、右半,要么跨越中点。 ```java class Solution { public int maxSubArray(int[] nums) { return divide(nums, 0, nums.length - 1); } private int divide(int[] nums, int lo, int hi) { if (lo == hi) return nums[lo]; int mid = lo + (hi - lo) / 2; int left = divide(nums, lo, mid); int right = divide(nums, mid + 1, hi); int cross = crossMax(nums, lo, mid, hi); return Math.max(Math.max(left, right), cross); } private int crossMax(int[] nums, int lo, int mid, int hi) { int leftSum = Integer.MIN_VALUE, sum = 0; for (int i = mid; i >= lo; i--) { sum += nums[i]; leftSum = Math.max(leftSum, sum); } int rightSum = Integer.MIN_VALUE; sum = 0; for (int i = mid + 1; i <= hi; i++) { sum += nums[i]; rightSum = Math.max(rightSum, sum); } return leftSum + rightSum; } } ``` ## 解法对比 | | 解法一(Kadane) | 解法二(分治) | |--|--------|--------| | 时间复杂度 | O(n) | O(n log n) | | 空间复杂度 | O(1) | O(log n)(递归栈) | | 特点 | 最优,简洁 | 可并行化,适合分布式场景 |
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入