LeetCode 算法：最大子数组和c++

原题链接🔗：最大子数组和
难度：中等⭐️⭐️

题目

给你一个整数数组 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⁵
-10⁴ <= nums[i] <= 10⁴

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

题解

动态规划法

1. 题解：Kadane 算法。
2. 复杂度：时间复杂度为 O(n)，空间复杂度为 O(1)
3. 代码过程：

• 初始化变量：
  • currentMax：当前子数组的最大和，初始值为数组的第一个元素。
  • globalMax：全局最大子数组和，初始值同 currentMax。
• 遍历数组: 从数组的第二个元素开始遍历（如果数组不为空）。
• 更新当前最大和：对于数组中的每个元素 nums[i]，决定是将其加到当前子数组的末尾，还是从这个元素开始一个新的子数组。这可以通过比较 nums[i] 和 currentMax + nums[i] 来实现，取两者中的较大值作为新的 currentMax。
• 更新全局最大和：在每次迭代中，比较 currentMax 和 globalMax，将较大的值赋给 globalMax。
• 返回结果：遍历完成后，globalMax 将包含整个数组的最大子数组和。

4. c++ demo:

#include 
#include 
#include  // 用于 std::max 函数

// 函数返回最大子数组和
int maxSubArraySum(const std::vector<int>& nums) {
    if (nums.empty()) return 0;

    int currentMax = nums[0];
    int globalMax = nums[0];

    for (int i = 1; i < nums.size(); ++i) {
        // 选择当前元素自身或者加上之前的currentMax
        currentMax = std::max(nums[i], currentMax + nums[i]);
        // 更新全局最大值
        globalMax = std::max(globalMax, currentMax);
    }

    return globalMax;
}

// 主函数
int main() {
    // 测试用例
    std::vector<int> testArray = { -2,1,-3,4,-1,2,1,-5,4 };

    // 调用函数并打印结果
    int maxSum = maxSubArraySum(testArray);
    std::cout << "Maximum subarray sum is: " << maxSum << std::endl; // 应该输出 6，因为 [4,-1,2,1] 是最大子数组

    // 可以添加更多的测试用例来验证算法的正确性
    std::vector<int> testArray2 = { 1 };
    std::cout << "Maximum subarray sum is: " << maxSubArraySum(testArray2) << std::endl; // 应该输出 1

    std::vector<int> testArray3 = { 5,4,-1,7,8 };
    std::cout << "Maximum subarray sum is: " << maxSubArraySum(testArray3) << std::endl; // 应该输出 23

    std::vector<int> testArray4 = { -8 };
    std::cout << "Maximum subarray sum is: " << maxSubArraySum(testArray4) << std::endl; // 应该输出 -8

    std::vector<int> testArray5 = { -2, -3, 4, -1, -2, 1, 5, -3 };
    std::cout << "Maximum subarray sum is: " << maxSubArraySum(testArray5) << std::endl; // 应该输出 7

    return 0;
}

• 运行结果：

Maximum subarray sum is: 6
Maximum subarray sum is: 1
Maximum subarray sum is: 23
Maximum subarray sum is: -8
Maximum subarray sum is: 7

Kadane 算法

Kadane
算法是一种用于解决最大子数组和问题的有效算法。最大子数组和问题是指在给定的整数数组中找到一个连续子数组，使得该子数组的和最大。Kadane
算法通过动态规划的思想来解决这个问题，其核心思想是利用当前子数组的和来帮助确定后续子数组的最大和。

Kadane 算法的步骤：

1. 初始化：设置两个变量 currentMax 和 globalMax 来分别存储当前子数组的最大和以及全局最大和。初始时，这两个变量都设为数组的第一个元素。

2. 遍历数组：从数组的第二个元素开始遍历。

3. 更新当前最大和：对于当前遍历到的元素 nums[i]，决定是将其加到当前子数组的和中，还是从当前元素开始一个新的子数组。这可以通过比较 nums[i] 和
   currentMax + nums[i] 的大小来实现。如果 nums[i] 本身就大于 currentMax + nums[i]，说明当前子数组加上这个元素后的和会减小，因此应该从 nums[i] 开始一个新的子数组。

   更新公式为： [ \text{currentMax} = \max(\text{nums}[i],
   \text{currentMax} + \text{nums}[i]) ]

4. 更新全局最大和：每次更新完 currentMax 后，比较 currentMax 和 globalMax 的大小，并更新 globalMax。

5. 返回结果：遍历完成后，globalMax 将包含整个数组的最大子数组和。

Kadane 算法的特点：

• 时间复杂度：O(n)，其中 n 是数组的长度，因为算法只遍历一次数组。
• 空间复杂度：O(1)，只需要常数级别的额外空间。

Kadane 算法简洁且效率高，是解决最大子数组和问题的首选方法。