【力扣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 <= 105
104 <= 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 <= 104
intervals[i].length == 2
0 <= 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;}
};