【练习】力扣 热题100 最大子数组和

题目

给你一个整数数组 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 <= 105
• -104 <= nums[i]<= 104

来源：力扣 热题100 最大子数组和
——————————————————————

最大子数组和问题（Maximum Subarray Problem）是一个经典的算法问题，目标是在一个整数数组中找到具有最大和的连续子数组。以下是5种解法及其详细解释：

1. 暴力枚举法（数据量很大时，此题会超时）

思路

• 枚举所有可能的子数组，计算每个子数组的和，并记录最大值。
• 使用双重循环，外层循环确定子数组的起点，内层循环确定子数组的终点。

代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = INT_MIN; //int最小值
        for (int i = 0; i < nums.size(); i++) {
            int sum = 0;
            for (int j = i; j < nums.size(); j++) {
                sum += nums[j];
                maxSum = max(maxSum, sum);
            }
        }
        return maxSum;
    }
};

时间复杂度

• O(N^2)，其中 N 是数组的长度。
• 外层循环运行 N 次，内层循环平均运行 N/2 次。

空间复杂度

• O(1)，只使用了常数级别的额外空间。

2. 动态规划（Kadane 算法）（最优解）

思路

1. 使用动态规划的思想，原地修改数组 nums，将 nums[i] 更新为以 nums[i] 结尾的最大子数组和。
2. 如果 nums[i - 1] 大于 0，说明以 nums[i - 1] 结尾的子数组和对 nums[i] 有贡献，因此将其加到 nums[i] 上。
3. 在遍历过程中，记录 nums[i] 的最大值，即全局最大子数组和。

代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0]; // 全局最大子数组和

        // 动态规划：原地修改 nums[i] 为以 nums[i] 结尾的最大子数组和
        for (int i = 1; i < nums.size(); i++) {
            // 如果 nums[i - 1] 大于 0，则将其加到 nums[i] 上
            if (nums[i - 1] > 0) {
                nums[i] += nums[i - 1];
            }
            // 更新全局最大子数组和
            maxSum = max(maxSum, nums[i]);
        }

        return maxSum;
    }
};

时间复杂度

• O(N)，其中 N 是数组的长度。
• 只需遍历数组一次。

空间复杂度

• O(1)，只使用了常数级别的额外空间。

3. 分治法（拓展）

思路

• 将数组分成左右两部分，分别递归求解左右部分的最大子数组和。
• 最大子数组和可能出现在左半部分、右半部分，或者跨越左右两部分。
• 计算跨越左右两部分的最大子数组和时，需要从中间向左右扩展。

代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return divideAndConquer(nums, 0, nums.size() - 1);
    }

    int divideAndConquer(vector<int>& nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

        int mid = left + (right - left) / 2;

        // 分别计算左半部分和右半部分的最大子数组和
        int leftMax = divideAndConquer(nums, left, mid);
        int rightMax = divideAndConquer(nums, mid + 1, right);

        // 计算跨越左右两部分的最大子数组和
        int crossMax = maxCrossingSum(nums, left, mid, right);

        // 返回三者中的最大值
        return max({leftMax, rightMax, crossMax});
    }

    int maxCrossingSum(vector<int>& nums, int left, int mid, int right) {
        int leftSum = INT_MIN, rightSum = INT_MIN;
        int sum = 0;

        // 从中间向左扩展，计算左半部分的最大和
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = max(leftSum, sum);
        }

        sum = 0;
        // 从中间向右扩展，计算右半部分的最大和
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = max(rightSum, sum);
        }

        // 返回跨越左右两部分的最大和
        return leftSum + rightSum;
    }
};

时间复杂度

• O(N log N)，其中 N 是数组的长度。
• 分治法的时间复杂度由递归深度和每层的工作量决定。

空间复杂度

• O(log N)，递归调用栈的深度为 log N。

4. 前缀和优化（拓展）

思路

• 计算数组的前缀和数组 prefixSum，其中 prefixSum[i] 表示从 nums[0] 到 nums[i] 的和。
• 最大子数组和可以表示为 prefixSum[j] - prefixSum[i] 的最大值，其中 i < j。
• 在遍历过程中，维护 minPrefixSum，表示当前最小的前缀和。

代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int minPrefixSum = 0;
        int prefixSum = 0;

        for (int num : nums) {
            prefixSum += num; // 计算当前前缀和
            maxSum = max(maxSum, prefixSum - minPrefixSum); // 更新最大子数组和
            minPrefixSum = min(minPrefixSum, prefixSum); // 更新最小前缀和
        }

        return maxSum;
    }
};

时间复杂度

• O(N)，其中 N 是数组的长度。
• 只需遍历数组一次。

空间复杂度

• O(1)，只使用了常数级别的额外空间。

5. 贪心算法（拓展）

思路

• 遍历数组，维护当前子数组的和 currentSum。
• 如果 currentSum 小于 0，则重置为当前元素；否则，累加当前元素。
• 在遍历过程中，记录 currentSum 的最大值。

代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            // 如果当前子数组和小于 0，则重置为当前元素
            if (currentSum < 0) {
                currentSum = nums[i];
            } else {
                // 否则，累加当前元素
                currentSum += nums[i];
            }

            // 更新最大子数组和
            maxSum = max(maxSum, currentSum);
        }

        return maxSum;
    }
};

时间复杂度

• O(N)，其中 N 是数组的长度。
• 只需遍历数组一次。

空间复杂度

• O(1)，只使用了常数级别的额外空间。

6. 总结

• 推荐解法：动态规划（Kadane 算法），时间复杂度为 O(N)，空间复杂度为 O(1)，是最优解法。