🔗 最大子数组和

题目来源：53. 最大子数组和 – 力扣（LeetCode）

---

📌 题目描述

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

• 子数组 是数组中的一个连续部分。
• 要求的是所有连续子数组中，元素和最大的那个值。

---

✅ 示例解析

示例 1：

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

示例 2：

• 输入：nums = [1]
• 输出：1
• 解释：只有一个元素，最大和就是它本身。

示例 3：

• 输入：nums = [5,4,-1,7,8]
• 输出：23
• 解释：整个数组的和就是最大值：5+4+(-1)+7+8 = 23。

示例 4：

• 输入：nums = [-1]
• 输出：-1
• 解释：即使为负数，也必须选择至少一个元素。

---

⚠️ 提示

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴

---

💡 解法：动态规划（Kadane 算法）—— O(n) 时间，O(1) 空间

public class Solution {
    public int maxSubArray(int[] nums) {
        int sum = nums[0];
        int pre = 0;
        for (int p : nums) {
            pre = Math.max(pre + p, p);
            sum = Math.max(pre, sum);
        }
        return sum;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  仅需一次遍历数组，每个元素处理时间为 O(1)，整体为线性时间。
• 空间复杂度：O(1)
  只使用了两个变量 pre 和 sum，额外空间为常数。

---

🧩 解题思路

1. 核心思想：动态规划（Kadane 算法）
   定义 pre 表示以当前元素结尾的最大子数组和。
   对于每个元素 p，我们有两种选择：
   • 将 p 加入前面的子数组（和为 pre + p）
   • 从 p 重新开始一个新的子数组（和为 p）
     我们选择两者中更大的一个：pre = max(pre + p, p)
2. 状态转移：
   • 初始化 pre = 0（表示前面无元素）
   • 遍历每个元素 p：
     • 更新 pre = max(pre + p, p)
     • 更新全局最大值 sum = max(sum, pre)
3. 为什么这样是正确的？
   • 我们关心的是“以当前位置结尾”的最大和，因为下一个元素只能接在这个结尾后面。
   • 如果前面的和 pre 为负，那么加上它只会让当前和更小，不如从当前元素重新开始。
   • 因此，max(pre + p, p) 实际上是“贪心”地决定是否继承前面的子数组。
4. 举例说明：
   对于 nums = [-2,1,-3,4]：
   • p = -2: pre = max(0 + (-2), -2) = -2, sum = max(-2, -2) = -2
   • p = 1: pre = max(-2 + 1, 1) = 1, sum = max(1, -2) = 1
   • p = -3: pre = max(1 + (-3), -3) = -2, sum = max(-2, 1) = 1
   • p = 4: pre = max(-2 + 4, 4) = 4, sum = max(4, 1) = 4
     最终返回 4，对应子数组 [4]。
5. 边界处理：
   • 初始化 sum = nums[0] 是为了处理全为负数的情况。
   • pre 初始为 0，表示开始前无累加值。