首先提出一个简单的问题，之后在此基础上一步步进行拓展，整体上从易到难，逐渐深入。
问题一
给定 \(n\) 个区间 \([l_i,r_i]\) ，选出至多\(2\)个两两不重叠的区间 \([start_i, end_i]\)，每个区间由 \([l_x, r_y]\) 组成（ \(y\ge x\)），最大化 \(\sum (end_i - start_i)\)
分析
将\(n\)个区间放到数轴上可以看作\(2n\)个点，每个节点有相应的类型（左或右）、值的大小，同时由于限制选取的每个区间为 \([l_x,r_y]\)，为方便之后的处理可以按照给定区间的顺序将2n个节点进行排序。
要选择至多两个区间，可以通过选取两个区间的分割点，得到分割点左右区间收益之和，取最大值，具体实现可以维护两个长度为\(2n\)的数组\(MaxLeft\)和\(MaxRight\)，分别记录当前节点左区间和右区间可以取到的最大值，之后遍历所有\(2n\)个节点即可，时间复杂度为 \(O(n)\).
对于两个数组的维护，这里以MaxLeft数组为例说明，假设当前节点类型为左边界，那么就更新 \(MaxLeft [i]=MaxLeft [i-1]\)，同时更新 当前最小的 \(MinL\) ；当前节点若为右边界，则更新为当前节点的值减去\(MinL\)。
\[MaxLeft[i]=\left\{ \begin{array}[ll]\ MaxLeft [i-1]\quad \text{if}\ type_i= l \\ value_i-MinL\quad\ \text{if}\ type_i=r \end{array} \right. \]同理 \(MaxRight\) 的更新规则如下：
\[MaxRight[i]=\left\{ \begin{array}[ll]\ MaxRight [i+1]\quad \text{if}\ type_i= r \\ MaxR-value_i\quad\ \text{if}\ type_i=l \end{array} \right. \]之后遍历所有 \(2n\) 个节点，\(Result= Maxmize_i\quad MaxRight[i]+MaxLeft[i]\)
问题二
给定 \(n\) 个区间 \([l_i,r_i]\) ，选出至多\(k\)个两两不重叠的区间 \([start_i, end_i]\)，每个区间由 \([l_x, r_y]\) 组成（ \(y\ge x\)），最大化 \(\sum (end_i - start_i)\)
分析
与问题一唯一的区别是将区间的选择由\(2\)个变为了\(k\)个，这时便不能简单的枚举分割点了。这时的问题便需要使用动态规划的方法。
考虑 \(dp[i][j]\) 表示在选取前 \(i\) 个节点并选择 \(j\) 个区间得到的最大值，那么最终的结果为 \(dp[2n][k]\)
对于边界值 \(dp[i][0]=dp[0][j]=0, \forall i\in[1,2n],j\in[1,k]\).
之后考虑如何进行更新，如果该节点类型为左边界节点，那么在加入该节点后一定不会发生区间选择的变化，\(dp[i][j]=max(dp[i][j],dp[i-1][j])\) ； 如果该节点类型为右边界节点，假设该节点加入后不会发生区间选择的变化，那么\(dp[i][j]=max(dp[i][j],dp[i-1][j])\) ，如果会发生区间选择的变化，那么选择的第 \(j\) 个区间，便是当前节点与之前的某个左边界节点形成的一个新区间，通过遍历之前的左边界节点更新： $dp[i][j]=max(dp[i][j],dp[s-1][j-1]+value_i-value_s),\forall s\in[1,i],type_s=l $
因此最终的递推方程为：
\[dp[i][j]=\left\{ \begin{array}[ll]\ \begin{split} max(dp[i][j],dp[i][j-1]) \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \text{if}\ type_i=l\\ max(dp[i][j],dp[i][j-1],dp[s-1][j-1]+value_i-value_s)\quad \text{if}\ type_i=r \end{split} \end{array} \right. \]需要注意的是 \(s\in[1,i]\) 并且 \(\text{type}_i = l\) 。
最终的时间复杂度为 \(O(n^2k)\) ，这里可以通过某些数据结构（树/队列）来存储查询 \(dp[s-1][j-1]-value_s\) 的最大值，消除循环查询最大值，实现 \(log_n\) 的查询，时间复杂度可以优化到 \(O(nklog_n)\)
问题三
（1）给定一个数组，它的第 \(i\) 个元素是一支给定的股票在第 \(i\) 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
（2）给你一个整数数组 \(prices\) 和一个整数 \(k\) ，其中 \(prices[i]\) 是某支给定的股票在第 \(i\) 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 \(k\) 笔交易。也就是说，你最多可以买 \(k\) 次，卖 \(k\) 次。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
分析
上面两个问题是 LeetCode 中的两道题，题目链接如下：
仔细分析可以发现，买一支股票然后卖掉，如果想要得到最大收益，肯定要在低价时买入，在高价时卖出，而从低价到高价期间的值是没什么意义的；同时，在一支股票后面的值如果比前面的值要小（\(prices[i+1]\le prices[i]\)），那么购买前面的股票是没什么意义的，一定不是最优的。所以，对于给定的prices数组，按照这两个原则进行处理后，便得到了m对数组 \((l_i,r_i)\)，并且 \(l_i<r_i,r_i>l_{i+1}\)，这样这两个问题便转化为了前面的问题一和问题二，问题解决。
标签：题目,探索,end,算法,区间,quad,type,节点,dp From： https://www.cnblogs.com/sunmk/p/18671486