🎯 最大子数组和算法可视化

一个交互式的可视化应用，帮助你理解 LeetCode 53 题的最大子数组和算法（Kadane's Algorithm）。

🎉 在线演示

👉 点击查看在线演示

📚 算法简介

Kadane 算法是一个经典的动态规划算法，用于在 O(n) 时间复杂度内找到一个数组中具有最大和的连续子数组。

核心思想

算法的核心思想非常简单而优雅：

• 如果当前累积和变成负数，就放弃这段子数组，从下一个元素重新开始
• 为什么？因为负数只会让后续的和变小，不如重新开始
• 在遍历过程中记录最大和，最终返回这个最大值

算法步骤

1. 初始化两个变量：

   • currentSum = 0：当前子数组的和
   • maxSum = nums[0]：到目前为止找到的最大和

2. 遍历数组的每个元素：

   • 将当前元素加到 currentSum 上
   • 如果 currentSum 小于当前元素本身，说明之前的累积是负担，重新从当前元素开始
   • 更新 maxSum 为 currentSum 和 maxSum 中的较大值

3. 返回 maxSum

时间和空间复杂度

• 时间复杂度：O(n) - 只需遍历一次数组
• 空间复杂度：O(1) - 只需要常数个变量

🚀 快速开始

安装依赖

npm install

启动开发服务器

npm run dev

启动后，在浏览器中打开显示的本地地址（通常是 http://localhost:5173）。

构建生产版本

npm run build

预览生产版本

npm run preview

🎮 功能特性

📊 交互式可视化

• 动态柱状图：使用 D3.js 绘制数组元素的柱状图
• 颜色编码：
  • 🟡 黄色边框：当前正在处理的元素
  • 🔵 蓝色：当前子数组范围
  • 🟢 绿色：找到的最佳子数组
  • 🔴 红色/粉色：负数元素

🎬 动画控制

• ▶️ 播放/暂停：自动演示算法执行过程
• ⏮️ 上一步/下一步：逐步查看算法执行
• 🔄 重置：回到初始状态
• 🎚️ 速度调节：调整动画播放速度（0.3x - 5x）
• 📊 进度条：直接跳转到任意步骤

📝 详细说明

• 💡 算法原理：完整的 Kadane 算法原理讲解
• 📖 伪代码：清晰的算法伪代码
• 📌 步骤说明：每一步都有详细的文字解释
• 🎯 实时状态：显示当前和、最大和等关键变量

🔢 多种示例

预设了多个测试用例：

• 示例 1：[-2, 1, -3, 4, -1, 2, 1, -5, 4] - LeetCode 经典示例
• 示例 2：[1] - 单元素数组
• 示例 3：[5, 4, -1, 7, 8] - 全部正数居多
• 复杂示例：[-3, 2, -1, 4, -2, 3, -5, 6, -1, 2] - 正负混合

🛠️ 技术栈

• React 18：现代化的用户界面库
• TypeScript：类型安全的 JavaScript 超集
• D3.js：强大的数据可视化库
• Vite：极速的前端构建工具
• Lucide React：美观的图标库

📖 学习建议

1. 先理解原理：点击"显示算法说明"按钮，仔细阅读算法原理
2. 慢速观看：第一次使用较慢的速度（0.5x - 1x）完整观看一遍
3. 逐步分析：使用"上一步/下一步"按钮，仔细分析每一步的变化
4. 多试几个例子：尝试不同的示例，理解算法在不同情况下的行为
5. 关注关键时刻：特别注意当 currentSum 变负数时算法的决策

💡 关键洞察

为什么要重新开始？

当累积和变成负数时，继续累加只会拖累后面的元素。例如：

[-2, 1] vs [1]
累积和 -1  vs 累积和 1

显然从 1 重新开始更好！

为什么只需要一次遍历？

因为算法利用了贪心策略：

• 在每个位置，我们只关心"以当前元素结尾的最大子数组和"
• 这个值只依赖于前一个位置的结果
• 不需要回头重新计算

🤔 常见问题

Q: 如果数组全是负数怎么办？
A: 算法会返回最大的那个负数（即最小损失）。

Q: 能找到多个具有相同最大和的子数组吗？
A: 标准算法只返回最大和的值，不返回具体子数组。如果需要找到所有解，需要修改算法记录所有达到最大和的子数组。

Q: 这个算法能用于其他问题吗？
A: 是的！Kadane 算法的思想可以应用到许多类似的动态规划问题中，比如最大乘积子数组、买卖股票等。

🌟 进阶挑战

理解了基础算法后，可以尝试：

1. 最大乘积子数组（LeetCode 152）：类似问题，但需要同时跟踪最大和最小值
2. 环形子数组的最大和（LeetCode 918）：在环形数组中找最大子数组和
3. 分治法实现：尝试用 O(n log n) 的分治法实现相同功能

📄 License

MIT License

🙏 致谢

感谢 Joseph Kadane 教授在 1984 年提出这个优雅的算法！

---

享受学习的过程！如果这个可视化工具帮助了你，别忘了给个 ⭐ Star！