【力扣Hot 100】普通数组1
1. 最大子数组和
给你一个整数数组 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 <= 105104 <= nums[i] <= 104
题解：
动态规划：
用g[i]表示：以 i 结尾的连续最长子序列的和
那么 g[i] = max(g[i - 1] + nums[i], nums[i])
意思是：以 i 结尾的连续最长子序列的和，等于，以i - 1结尾的连续最长子序列的和 加上 第i个数，和，第i个数，之间的最大值。
注意，因为数组nums是从0开始的，所以用 g[i] 表示：以 i - 1结尾的连续最长子序列的和
同时nums[i]表示第i个数
关系式变成： g[i + 1] = max(g[i] + nums[i], nums[i])
意思是：以 i 结尾的连续最长子序列的和，等于，以i - 1结尾的连续最长子序列的和 加上 第i个数，和，第i个数，之间的最大值。
const int N = 1e5 + 10;
int g[N];
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int ans = nums[0];
for(int i = 0; i < n; i ++ ) {
g[i + 1] = max(g[i] + nums[i], nums[i]);
ans = max(ans, g[i + 1]);
}
return ans;
}
};
发现，g[i + 1]只受到前面一个数 g[i] 的影响，因此数组g可以省去：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = nums[0], pre = 0;
int n = nums.size();
for(int i = 0; i < n; i ++ ) {
pre = max(pre + nums[i], nums[i]);
ans = max(ans, pre);
}
return ans;
}
};
2. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
题解
做题的时候可以画图整理一下思路。
先按区间左端点排序。
用 bg, ed 记录当前的区间的左右端点。
遍历数组中的每个区间，分别判断以下三种情况：
-
bg———ed
v0———v1
v0 > ed，那么把 {bg, ed} 存入 ans，并更新 bg = v0, ed = v1
-
bg———ed
v0————v1
v0 < ed，并且v1 > ed，那么更新ed为v1: ed = v1
-
bg—————ed
v0——v1
v1 < ed，不用管
因为区间是按左端点排序的，所以 v0 一定大于bg，不用管
初始化 bg, ed 时，把它们设为特别小的值，在将 {bg, ed} 存入 ans 时要判断是不是最初的bg, ed
代码：
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> ans;
sort(intervals.begin(), intervals.end());
int bg = -1e5, ed = -1e5;
for(int i = 0; i < intervals.size(); i ++ ) {
auto &v = intervals[i];
if(v[0] > ed) {
// 第一种情况
if(i) ans.push_back({bg, ed});
bg = v[0];
ed = v[1];
} else {
if(v[1] > ed) {
// 第二种情况
ed = v[1];
}
}
}
ans.push_back({bg, ed});
return ans;
}
};