最长上升子序列（Longest Increasing Subsequence，LIS）

原文oi wiki:LIS

简单情形

在最长上升子序列问题中，我们引入两个关键变量 i 和 j。这里，i 表示以其作为结尾的最长上升子序列的长度，而 j 则作为连接点，在构建最长上升子序列的过程中起着重要作用。

需要特别注意的是，dp[mx] 并不一定就是最终答案。在得出所有以不同元素结尾的最长上升子序列长度后，我们需要遍历整个结果数组，才能找出真正的最长上升子序列长度。

 for(int i=1;i<=n;++i)
    {
    	dp[i]=1;
    	for(int j=1;j<i;++j)
    	{
    		if(a[j]<=a[i])
    		dp[i]=max(dp[i],dp[j]+1);
    	}
    }
    int ans=0;
    for(int i=1;i<=n;++i)ans=max(ans,dp[i]);

困难情形：单调栈二分动态规划核心思想

1. 单调栈

我们维护一个单调递增的栈 stk，这个栈用于存储当前有可能构成最长上升子序列的元素。栈的关键特性在于其中的元素始终保持单调递增，借助这一特性，我们能够快速定位当前元素在栈中应该插入的位置，从而高效地构建潜在的最长上升子序列。

2. 二分查找

对于序列中的每个元素 a[i]，我们运用二分查找算法在单调栈 stk 中找出第一个大于等于 a[i] 的位置。若该位置位于栈内，我们用 a[i] 替换此位置的元素；若不存在这样的位置，即 a[i] 大于栈内所有元素，我们将 a[i] 压入栈中。通过这种方式，不断优化栈内元素，逐步逼近最长上升子序列。

3. 动态规划

通过巧妙维护单调栈，我们能够动态地更新最长上升子序列的长度。在整个过程中，我们要牢记三个核心要点：

• 二分查找位置：准确运用二分查找确定元素在栈中的合适位置。
• 更长则更新：当遇到能使上升子序列更长的元素时，要及时更新相关信息。这里强调的是不仅要长度更长，同时元素的值相对更“矮”，这样能为后续构建更长的子序列提供更多可能性。
• 取代栈内的值：当找到合适位置时，用新元素替换栈内相应位置的元素，优化栈的结构。

for(int i=1;i<=n;++i)
	    {
	    	int pos=lower_bound(stk+1,stk+1+top,a[i])-stk;
	    	/*找到第一个大于等于a[i]的位置,注意，严格上升!如果是等元素则返回的是栈顶也就不会是top+1,如果题目说的是
	    	不降则就要找到第一个大于a[i]的位置取代,届时用upper_bound即可*/
	    	if(pos==top+1)top++;//如果长度比top更长就取代这个位置,这一行是更新最大长度
	    	stk[pos]=a[i];//取代
	    	ans=max(ans,top);
	    }

狄尔沃斯定理

狄尔沃斯定理为我们理解最长上升子序列及其相关概念提供了新的视角，具体内容如下：

• 最长不升子序列的最小覆盖数等于最长上升子序列的长度。
• 最长不降子序列的最小覆盖数等于最长下降子序列的长度。

这个定理建立了不同类型子序列之间的内在联系，有助于我们更深入地理解序列的结构和性质，在解决相关问题时提供了有力的理论支持。