coder-msc
diff --git a/‎README.md
Lines changed: 2 additions & 0 deletions b/‎README.md
Lines changed: 2 additions & 0 deletions
diff --git a/‎pics/131.分割回文串.png
10.2 KB b/‎pics/131.分割回文串.png
10.2 KB
diff --git a/‎pics/57.插入区间.png
29.5 KB b/‎pics/57.插入区间.png
29.5 KB
diff --git a/‎pics/57.插入区间1.png
25.5 KB b/‎pics/57.插入区间1.png
25.5 KB
diff --git a/‎pics/941.有效的山脉数组.png
61.5 KB b/‎pics/941.有效的山脉数组.png
61.5 KB
diff --git a/‎problems/0053.最大子序和.md
Lines changed: 31 additions & 7 deletions b/‎problems/0053.最大子序和.md
Lines changed: 31 additions & 7 deletions
diff --git a/‎problems/0057.插入区间.md
Lines changed: 86 additions & 0 deletions b/‎problems/0057.插入区间.md
Lines changed: 86 additions & 0 deletions
@@ -137,6 +137,7 @@
     * [回溯算法：电话号码的字母组合](https://mp.weixin.qq.com/s/e2ua2cmkE_vpYjM3j6HY0A)
     * [本周小结！（回溯算法系列一）](https://mp.weixin.qq.com/s/m2GnTJdkYhAamustbb6lmw)
     * [回溯算法：求组合总和（二）](https://mp.weixin.qq.com/s/FLg8G6EjVcxBjwCbzpACPw)
+    * [回溯算法：求组合总和（三）](https://mp.weixin.qq.com/s/_1zPYk70NvHsdY8UWVGXmQ)
 
 （持续更新中....）
 
@@ -405,6 +406,7 @@
 |[0841.钥匙和房间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0841.钥匙和房间.md) |孤岛问题 |中等|**bfs** **dfs**|
 |[0844.比较含退格的字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0844.比较含退格的字符串.md) |字符串 |简单|**栈** **双指针优化** 使用栈的思路但没有必要使用栈|
 |[0925.长按键入](https://github.com/youngyangyang04/leetcode/blob/master/problems/0925.长按键入.md) |字符串 |简单|**双指针/模拟** 是一道模拟类型的题目|
+|[0941.有效的山脉数组](https://github.com/youngyangyang04/leetcode/blob/master/problems/0941.有效的山脉数组.md) |数组 |简单|**双指针**|
 |[0968.监控二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0968.监控二叉树.md) |二叉树 |困难|**贪心** 贪心与二叉树的结合|
 |[0977.有序数组的平方](https://github.com/youngyangyang04/leetcode/blob/master/problems/0977.有序数组的平方.md) |数组 |中等|**双指针** 还是比较巧妙的|
 |[1002.查找常用字符](https://github.com/youngyangyang04/leetcode/blob/master/problems/1002.查找常用字符.md) |栈 |简单|**栈**|
 
@@ -2,6 +2,8 @@
 ## 题目地址 
 https://leetcode-cn.com/problems/maximum-subarray/
 
+# 思路
+
 ## 暴力解法 
 
 暴力解法的思路，第一层for 就是设置起始位置，第二层for循环遍历数组寻找最大值 
@@ -27,12 +29,30 @@ public:
 ```
 
 ## 贪心解法 
+
 贪心解法，其实不是很好理解， 看上面暴力的解法是两层for循环，那如何省掉一层for循环呢 
-   
-其实**暴力解法中设置起始位置这个for循环是可以省略掉的**，这也是关键的一步，有了这个思路之后，就可以看一下代码了
 
-时间复杂度：O(n) 
-空间复杂度：O(1)
+**贪心贪的是哪里呢？**
+
+如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！
+
+同样的道理，遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从头累积count了（也就是此时count要归0），因为已经变为负数的count，只会拖累总和。
+
+相当于是不断调整区间的起始位置。 
+
+
+**那有同学问了，区间终止位置不用调整么？ 如何才能得到最大子序和呢？** 
+
+区间的终止位置，其实就是如果count取到最大值了，用result记录一下就可以了。
+
+如动画所示：
+
+<img src='../video/53.最大子序和.gif' width=600> </img></div>
+
+红色的其实位置就是贪心每次取count为正数的时候，开始一个区间的统计。
+
+不难写出如下C++代码（关键地方已经注释）
+
 ```
 class Solution {
 public:
@@ -41,14 +61,18 @@ public:
         int count = 0;
         for (int i = 0; i < nums.size(); i++) {
             count += nums[i];
-            if (count > result) { // 相当于每次取各个终点的最大值
+            if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
                 result = count;
             }
-            if (count <= 0) count = 0; // 相当于重置起点，因为遇到负数一定是拉低总体数值的
+            if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
         }
         return result;
     }
 };
 ```
-> 更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
+时间复杂度：O(n) 
+空间复杂度：O(1)
+
+> 我是[程序员Carl](https://github.com/youngyangyang04)，组队刷题可以找我，本文[leetcode刷题攻略](https://github.com/youngyangyang04/leetcode-master)已收录，更多[精彩算法文章](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect)尽在：[代码随想录](https://img-blog.csdnimg.cn/20200815195519696.png)，期待你的关注！
+
 
@@ -0,0 +1,86 @@
+
+这道题目合并的情况有很多种，想想都让人头疼。 
+
+我把这道题目化为三步：
+
+## 步骤一：找到需要合并的区间 
+
+找到插入区间需要插入或者合并的位置。 
+
+代码如下：
+
+```
+int index = 0; // intervals的索引
+while (index < intervals.size() && intervals[index][1] < newInterval[0]) {
+    result.push_back(intervals[index++]);
+}
+```
+
+此时intervals[index]就需要合并的区间了 
+
+## 步骤二：合并区间
+
+合并区间还有两种情况
+
+1. intervals[index]需要合并，如图：
+
+<img src='../pics/57.插入区间.png' width=600> </img></div>
+
+对于这种情况，只要是intervals[index]起始位置 <= newInterval终止位置，就要一直合并下去。
+
+代码如下：
+
+```
+while (index < intervals.size() && intervals[index][0] <= newInterval[1]) { // 注意防止越界
+    newInterval[0] = min(intervals[index][0], newInterval[0]);
+    newInterval[1] = max(intervals[index][1], newInterval[1]);
+    index++;
+}
+```
+合并之后，将newInterval放入result就可以了
+
+2. intervals[index]不用合并，插入区间直接插入就行，如图：
+
+<img src='../pics/57.插入区间1.png' width=600> </img></div>
+
+对于这种情况，就直接把newInterval放入result就可以了
+
+## 步骤三：处理合并区间之后的区间 
+
+合并之后，就应该把合并之后的区间，以此加入result中。
+
+代码如下：
+
+```
+while (index < intervals.size()) {
+    result.push_back(intervals[index++]);
+}
+```
+
+# 整体C++代码
+
+```
+class Solution {
+public:
+    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
+        vector<vector<int>> result;
+        int index = 0; // intervals的索引
+        // 步骤一：找到需要合并的区间
+        while (index < intervals.size() && intervals[index][1] < newInterval[0]) {
+            result.push_back(intervals[index++]);
+        }
+        // 步骤二：合并区间
+        while (index < intervals.size() && intervals[index][0] <= newInterval[1]) {
+            newInterval[0] = min(intervals[index][0], newInterval[0]);
+            newInterval[1] = max(intervals[index][1], newInterval[1]);
+            index++;
+        }
+        result.push_back(newInterval);
+        // 步骤三：处理合并区间之后的区间
+        while (index < intervals.size()) {
+            result.push_back(intervals[index++]);
+        }
+        return result;
+    }
+};
+```