题目描述
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
示例 1
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
示例 2
输入：nums = [1]
输出：1
示例 3
输入：nums = [5,4,-1,7,8]
输出：23
核心考点
- 贪心算法的应用（局部最优推导全局最优）；
- 动态规划的状态定义与转移；
- 时间复杂度的优化（从 O(n²) 到 O(n)）。
解题思路
1. 暴力解法
遍历所有可能的连续子数组，计算每个子数组的和，记录最大值。
具体步骤：
- 外层循环控制子数组的起始位置（i 从 0 到 nums.length-1）；
- 内层循环控制子数组的结束位置（j 从 i 到 nums.length-1）；
- 在遍历过程中，累加子数组的和（从 i 到 j），并实时更新最大和；
- 遍历结束后，返回最大和。
优点：逻辑简单，容易理解。 缺点：时间复杂度 O(n²)，当数组长度较大时会超时。
2. 动态规划
动态规划的核心是'状态定义'和'状态转移方程'。
第一步：定义状态 设 dp[i] 表示'以第 i 个元素结尾的连续子数组的最大和'。
第二步：推导状态转移方程 对于第 i 个元素，有两种选择：
- 将第 i 个元素加入到以 i-1 结尾的子数组中（即 dp[i-1] + nums[i]）；
- 不加入前序子数组，单独以第 i 个元素作为新的子数组（即 nums[i]）。
取两者中的最大值： dp[i] = max(dp[i-1] + nums[i], nums[i])
第三步：初始化与结果计算
- 初始化：dp[0] = nums[0]；
- 结果：遍历 dp 数组，取其中的最大值。
优化点：不用额外开辟 dp 数组，用一个变量临时存储 dp[i-1] 的值，将空间复杂度从 O(n) 优化到 O(1)。
3. 贪心算法
贪心算法的核心是'局部最优解推导全局最优解'。当前子数组的和为负数时，放弃这个子数组，重新开始计算。
具体逻辑：
- 定义两个变量：currentSum（当前子数组的和）、maxSum（全局最大和）；
