【LeetCodeHot100】最大子数组和｜动态规划/贪心，Java实现！图解+代码，小白也能秒懂！

💻 [LeetCode Hot100] 最大子数组和｜动态规划/贪心，Java实现！图解+代码，小白也能秒懂！

✏️本文对应题目链接：最大子数组和

---

📌 题目描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

---

🧠 解题思路（图文分解） ❗ 核心难点

如何在O(n)时间复杂度内找到最大和的连续子数组？

---

方法一：动态规划（贪心思想）✨

关键步骤：

定义状态：currentMax 表示以当前元素结尾的子数组的最大和状态转移： 如果 currentMax > 0 → 当前元素加入子数组如果 currentMax ≤ 0 → 从当前元素重新开始子数组 更新全局最大值：globalMax 记录遍历过程中的最大值

---

图解动态规划

输入数组：

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

遍历过程：

i=0: currentMax=-2 → globalMax=-2 i=1: currentMax=max(1, -2+1)=1 → globalMax=1 i=2: currentMax=max(-3, 1-3)=-2 → globalMax=1 i=3: currentMax=max(4, -2+4)=4 → globalMax=4 i=4: currentMax=max(-1, 4-1)=3 → globalMax=4 i=5: currentMax=max(2, 3+2)=5 → globalMax=5 i=6: currentMax=max(1, 5+1)=6 → globalMax=6 i=7: currentMax=max(-5, 6-5)=1 → globalMax=6 i=8: currentMax=max(4, 1+4)=5 → globalMax=6

最终结果：

globalMax = 6

---

🚀 代码实现 class Solution { public int maxSubArray(int[] nums) { int currentMax = nums[0]; // 当前最大子数组和 int globalMax = nums[0]; // 全局最大子数组和 for (int i = 1; i < nums.length; i++) { // 动态规划核心逻辑：选择继续累加或重新开始 currentMax = Math.max(nums[i], currentMax + nums[i]); // 更新全局最大值 globalMax = Math.max(globalMax, currentMax); } return globalMax; } }

---

💡 复杂度分析 时间复杂度：O(n) → 只需遍历数组一次空间复杂度：O(1) → 仅使用常数空间

---

方法二：分治法（进阶思路）

关键思路：将数组分成左右两部分，分别求解左半部分、右半部分和跨越中间的最大子数组和。

class Solution { public int maxSubArray(int[] nums) { return divideAndConquer(nums, 0, nums.length - 1); } private int divideAndConquer(int[] nums, int left, int right) { if (left == right) return nums[left]; int mid = left + (right - left) / 2; int leftMax = divideAndConquer(nums, left, mid); int rightMax = divideAndConquer(nums, mid + 1, right); int crossMax = maxCrossingSum(nums, left, mid, right); return Math.max(Math.max(leftMax, rightMax), crossMax); } private int maxCrossingSum(int[] nums, int left, int mid, int right) { int leftSum = Integer.MIN_VALUE; int currentSum = 0; for (int i = mid; i >= left; i--) { currentSum += nums[i]; leftSum = Math.max(leftSum, currentSum); } int rightSum = Integer.MIN_VALUE; currentSum = 0; for (int i = mid + 1; i <= right; i++) { currentSum += nums[i]; rightSum = Math.max(rightSum, currentSum); } return leftSum + rightSum; } }

---

🌟 总结要点

✅ 贪心思想核心：当累计和为负数时，立即放弃当前子序列 ✅ 分治法适用场景：大数据量分布式计算（时间复杂度O(n log n)） ✅ 适用场景：股票买卖、信号处理等求最大连续区间和问题

---