LeetCode题练习与总结：最大子数组和

一、题目描述

给你一个整数数组 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

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

二、解题思路

为了解决这个问题，我们可以使用 Kadane's Algorithm，这是一种高效且经典的动态规划算法。下面是这个算法的详细步骤和解题思路：

1. 初始化变量：

• maxSoFar：用来存储遍历过程中遇到的最大子数组和，初始值设为数组的第一个元素。
• currentMax：用来存储以当前元素结尾的最大子数组和，初始值也设为数组的第一个元素。

2. 遍历数组：

• 从数组的第二个元素开始遍历数组 nums。
• 对于每个元素 nums[i]，我们计算 currentMax，即以当前元素结尾的最大子数组和。这是通过比较当前元素本身和当前元素与之前的最大子数组和的和来决定的，即 currentMax = max(nums[i], currentMax + nums[i])。这样做的目的是决定是否将当前元素加入到之前的子数组中，或者是开始一个新的子数组。
• 接着，我们更新 maxSoFar，即遍历过程中遇到的最大子数组和。这是通过比较 maxSoFar 和 currentMax 来实现的，即 maxSoFar = max(maxSoFar, currentMax)。这确保了我们记录下遇到的所有子数组和中的最大值。

3. 返回结果：

• 遍历完成后，maxSoFar 将包含最大子数组和，我们将其作为函数的返回值。

三、具体代码

class Solution {
    public int maxSubArray(int[] nums) {
        // 初始化 maxSoFar 和 currentMax 为数组的第一个元素
        int maxSoFar = nums[0];
        int currentMax = nums[0];

        // 从数组的第二个元素开始遍历
        for (int i = 1; i < nums.length; i++) {
            // 更新 currentMax
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            // 更新 maxSoFar
            maxSoFar = Math.max(maxSoFar, currentMax);
        }

        // 返回最大子数组和
        return maxSoFar;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 代码中有一个单层循环，它从数组的第二个元素开始，一直遍历到数组的最后一个元素。
• 循环的每次迭代中，都包含了常数时间的计算，包括一次 Math.max 函数调用和一次赋值操作。
• 因此，整个循环的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。

2. 空间复杂度

• 代码中使用了两个额外的变量 maxSoFar 和 currentMax，它们的空间需求都是 O(1)。
• 没有使用任何依赖于输入数组长度的额外数据结构，如数组或列表。
• 因此，整个算法的空间复杂度是 O(1)。

五、总结知识点

1. 数组遍历：代码通过一个 for 循环遍历数组 nums，从第二个元素开始，直到数组的最后一个元素。这是处理数组或序列数据的常见方法。

2. 动态规划：Kadane's Algorithm 是解决最大子数组和问题的一种动态规划方法。动态规划是一种通过将问题分解为重叠的子问题，并存储子问题的解（通常是在一个表格中）来避免重复计算的算法策略。

3. 双变量维护：在遍历过程中，代码使用两个变量 maxSoFar 和 currentMax 来维护最大子数组和的信息。

• maxSoFar 用来记录遍历到目前为止遇到的最大子数组和。
• currentMax 用来记录以当前遍历到的元素结尾的最大子数组和。

4. 条件表达式和 Math.max 函数：代码中使用了 Math.max 函数来获取两个值中的最大值。这是在更新 currentMax 和 maxSoFar 时决定是否包含当前元素或开始新子数组的关键。

5. 返回值：函数的返回值是 maxSoFar，它代表了整个数组中具有最大和的连续子数组的和。

6. 边界条件处理：虽然代码中没有显式处理边界条件，但是由于 maxSoFar 和 currentMax 都是用数组的第一个元素初始化的，因此算法已经隐式地处理了当数组只有一个元素时的情况。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。