简单网站建设官网_汕头网站建设和运营_seo怎么收费seo_实时seo排名点击软件

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

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

---

📌 题目描述

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

示例：

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

---

🧠 解题思路（图文分解）

❗ 核心难点

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

---

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

关键步骤：

1. 定义状态：currentMax 表示以当前元素结尾的子数组的最大和
2. 状态转移：
   • 如果 currentMax > 0 → 当前元素加入子数组
   • 如果 currentMax ≤ 0 → 从当前元素重新开始子数组
3. 更新全局最大值：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)）
✅ 适用场景：股票买卖、信号处理等求最大连续区间和问题

---