LeetCode——Hot 100【合并区间 最大子数组和】

题目（一）

题目链接：合并区间

区间合并是算法面试中非常经典的问题，本文将详细讲解如何解决这一问题，包括解题思路、代码实现以及关键知识点的回顾。

解题思路

暴力解法：

遍历vetcor中的每一对区间，判断它们是否重叠（若区间 A 的起始值 ≤ 区间 B 的结束值，且区间 B 的起始值 ≤ 区间 A 的结束值，则认为重叠）。 若发现重叠区间，将它们合并为一个新区间（新区间的起始值为两区间起始值的最小值，结束值为两区间结束值的最大值），加入到结果集中。 不断重复步上述步骤，直到遍历完所有区间后未发现任何重叠，此时结果集即为合并后的区间。 上述就是暴力解法，显而易见效率较低，时间复杂度通常为 O(n²)（需多次遍历 n 个区间，每次检查 n² 对区间），这里就不做介绍了。

优化解法：

排序区间：首先按照区间的起始值对所有区间进行升序排序。排序后，所有可能重叠的区间会相邻出现，这是后续合并的基础。

遍历合并：遍历排序后的区间，对于每个区间，判断它是否能与结果集中的最后一个区间合并：如果结果集为空，或者当前区间与结果集中最后一个区间不重叠，则直接将当前区间加入结果集，如果当前区间与结果集中最后一个区间重叠，则合并这两个区间（更新结果集中最后一个区间的结束值）。

算法执行过程实例：

代码实现

class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
// 用于存储合并后的结果
vector<vector<int>> result;

// 步骤1：按区间起始值排序
sort(intervals.begin(), intervals.end());

// 步骤2：遍历并合并区间
for (int i = 0; i < intervals.size(); i++) {
// 当前区间的起始值和结束值
int currentStart = intervals[i][0];
int currentEnd = intervals[i][1];

// 情况1：结果集为空，或当前区间与结果集中最后一个区间不重叠
if (result.empty() || result.back()[1] < currentStart) {
// 直接将当前区间加入结果集
result.push_back({currentStart, currentEnd});
}
// 情况2：当前区间与结果集中最后一个区间重叠，需要合并
else {
// 更新结果集中最后一个区间的结束值为较大的那个结束值
result.back()[1] = max(currentEnd, result.back()[1]);
}
}

return result;
}
};

题目（二）

题目链接：最大子数组和

解题思路

暴力解法：

1.枚举所有子数组 对于给定的整数数组nums，最大子数组和的暴力解法是通过枚举所有可能的连续子数组。设数组nums的长度为n，那么子数组的起始位置可以从 0 到n – 1，对于每个起始位置i，子数组的结束位置可以从i到n – 1。这样就可以通过两层嵌套的循环来枚举所有的子数组。 2.计算子数组和并更新最大值 对于每一个枚举出来的子数组，计算它的和。用一个变量maxSum来记录目前找到的最大子数组和，每次计算出一个子数组的和后，将其与maxSum比较，如果大于maxSum，则更新maxSum。

最优解法：

使用动态规划的思想来解决这个问题。 定义一个状态变量来表示包含当前元素的最大子数组和。 状态转移方程： 对于数组中的每个元素nums[i]，包含它的最大子数组和有两种情况： 它自己单独作为一个子数组，即nums[i]。 它和前面的最大子数组和相加，即nums[i]+a（这里a表示包含前一个元素的最大子数组和）。 取这两种情况中的最大值作为包含当前元素的最大子数组和，即a = max(nums[i], nums[i]+a)。 在每次计算出包含当前元素的最大子数组和a后，再与全局最大的子数组和maxvalue进行比较，更新maxvalue，即maxvalue = max(a, maxvalue)。

示例分析： 以nums = [-2,1,-3,4,-1,2,1,-5,4]为例： 初始化a = 0，maxvalue=-2。 当i = 0时，s=-2，a = max(-2 + 0,-2)=-2，maxvalue = max(-2,-2)=-2。 当i = 1时，s = 1，a = max(1 + (-2),1)=1，maxvalue = max(1,-2)=1。 当i = 2时，s=-3，a = max(-3 + 1,-3)=-2，maxvalue = max(-2,1)=1。 当i = 3时，s = 4，a = max(4+(-2),4)=4，maxvalue = max(4,1)=4。 依此类推，直到遍历完整个数组，最终得到maxvalue = 6，对应的最大子数组是[4,-1,2,1]。

代码实现

class Solution {
public:
/**
* 寻找数组中具有最大和的连续子数组（子数组最少包含一个元素）
* @param nums 输入的整数数组
* @return 最大子数组的和
*/
int maxSubArray(vector<int>& nums) {
// a用于记录「包含当前元素的最大子数组和」
// 初始化为0，后续会根据第一个元素动态更新
int a = 0;

// maxvalue用于记录全局的最大子数组和
// 初始化为数组第一个元素，确保至少有一个元素被考虑
int maxvalue = nums[0];

// 遍历数组中的每个元素
for (auto& s : nums) {
// 核心逻辑：对于当前元素s，有两种选择
// 1. 将s加入到之前的子数组中（s + a）
// 2. 以s为起点重新开始一个子数组（s）
// 取两种选择中的最大值，更新a
a = max(s + a, s);

// 更新全局最大值：比较当前子数组和与历史最大值
maxvalue = max(a, maxvalue);
}

// 返回全局最大子数组和
return maxvalue;
}
};