从dp到贪心二分（最长上升子序列）

今天，我们要通过两种方法完成最长上升子序列这一道经典题目的解答。

什么是最长上升子序列

这时候，估计有的同学的疑问就来了，什么是上升子序列呢？
在百度百科上对最长上升子序列的定义是：
最长上升子序列（简称LIS）在计算机科学上是指一个序列中最长的单调递增的子序列。是不是很抽象？我们来举几个栗子：1 2 3 4 5就是一个最长上升子序列，1 4 2 5 7就不是一个最长上升子序列。
注意：最长上升子序列的长度是唯一的，但是最长上升子序列的序列是不唯一的，例如 6 8 9 2 3 7这个序列最长上升子序列的长度是3，但是它输出的序列会有6 8 9和2 3 7这两种序列。

用dp解最长上升子序列

接下来我们就移步至用dp解最长上升子序列。
dp 就是动态规划，简称动归。想必大家都学过线性dp吧（没学过的谨慎进入，不然怕你听不懂）在线性dp中，我们要用到状态转移方程式。今天我们同样用到状态转移方程式。
好了，扯了那么多废话，我们也该开始了。
首先给大家放张图：

看不懂很正常啊，因为我还没有开始讲。
栗子：将1 5 7 4 6 9这六个数存到a数组里边
首先第一步，我们先将dp数组初始化，此时dp里的序列：1 1 1 1 1 1；
第二步：a[2]是5,5比1要大,则dp[2]=dp[1]+1=2，此时dp序列为：1 2 1 1 1 1;
第三步：a[3]是7,7比5要大，则dp[3]=dp[2]+1=3,此时dp序列为：1 2 3 1 1 1；
第四步：a[4]是4,4比7要小，也比5小，但是4比1大，则dp[4]=dp[1]+1=2,此时dp序列为：1 2 3 2 1 1；
第五步：a[5]是6,6比4要大，则dp[5]=dp[4]+1=3,此时dp序列为：1 2 3 2 3 1；
第六步：a[6]是9,9比6大，则dp[6]=dp[5]+1=4,此时dp序列为：1 2 3 2 3 4；
由此可知，1 5 7 4 6 9这个序列的最长上升子序列的长度是4
懂了吗，我们来细致的讲一下。其实a数组的第一个数就不用管它了，直接初始化。咱们从第二个数开始，一次和前面的数判断（注意是从前往后直到这个数结束哦）。如果这个元素比它前面的那一个元素要大，直接用用那个元素下标的dp数组加1.若不是，则要继续往前找，用那个比他小的元素的dp数组下标加1；然后以此类推，直到循环结束；
循环结束之后我们就可以愉快的输出了

代码详解

咱们来到了愉快的解代码环节
首先咱们先输出a数组的序列，没什么可以讲的

cin>>n;
for(int i=1;i<=n;i++){
	cin>>a[i];
}
1
2
3
4

对了，别忘了初始化哟~~

cin>>n;
for(int i=1;i<=n;i++){
	cin>>a[i];
	dp[i]=1;
}
1
2
3
4
5

接着，按照我上面讲述的思路循环判断，代码如下：

if(a[j]<a[i]&&dp[j]+1>dp[i]){
	dp[i]=dp[j]+1;
	smax=max(smax,dp[i]);
}
1
2
3
4

此外，外面还要套两层循环：

for(int i=1;i<=n;i++){
	for(int j=1;j<i;j++){
		if(a[j]<a[i]&&dp[j]+1>dp[i]){
			dp[i]=dp[j]+1;
			smax=max(smax,dp[i]);
		}
	}
}
1
2
3
4
5
6
7
8

接下来输出就行了，不用我多说了。
接着是完整代码的呈现：

#include
using namespace std;
int a[10005],dp[10005],n,smax=-2e9;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[j]<a[i]&&dp[j]+1>dp[i]){
				dp[i]=dp[j]+1;
				smax=max(smax,dp[i]);
			}
		}
	}
	cout<<smax<<endl;
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

用贪心思想解决最长上升子序列

一旦题目数据再大一点，只要你提交上去就会发现：哦豁，超时了！！所以我们需要对代码进行优化，怎么优化呢？其实我也不知道我的dp思想如何优化，望大佬们指教，我只是一个学习c++一年半的初中生。
好了言归正传，既然这个方法使不得，我们就另寻出路。此时，我就想到了一个省时间的算法——二分！！！二分就不需要我多说了吧，家喻户晓的“中分头，背带裤，电脑面前学编程”说的就是我哈（bushi）。扯远了，下面来看一看我的思路：
我的思路是这样的，首先用a数组储存原序列。再进入另外一个数组里，这个进数组是有规定的。如果这个新的元素比当前的栈顶大，直接挤进去成为新的栈顶，如果没有栈顶大，就开始二分查找项目，查找大于它的元素且是比它大的元素中的最小数，然后把它替换掉，这样就可以更加扩大了两个元素之间的可容量。
蒙蒙的？举个栗子吧：
还是上面那个栗子：1 5 7 4 6 9
第一步：1进数组。
第二步：5大于1，成为新的栈顶，序列：1 5
第三步：7大于5，成为新的栈顶，序列：1 5 7
第四步：4小于7，二分查找，找到了5，将4替换5，序列：1 4 7
第五步：6小于7，二分查找，找到了7，将6替换7，序列：1 4 6
第六步：9大于6，成为新的栈顶，序列：1 4 6 9
可以知道该序列的最大上升子序列的长度为4.

代码详解

输入没啥多说的
接下来判断，如果大于栈顶，成为新的栈顶：

if(ans[len]<a[i]){
	ans[++len]=a[i];
}
1
2
3

否则，二分查找（注：这里要用到一个lower_bound函数，不会的去网上搜）：

else{
	int j=lower_bound(ans+1,ans+len+1,a[i])-ans;
	ans[j]=a[i];
}
1
2
3
4

接着，在外面套一层循环：

for(int i=1;i<=n;i++){
	if(ans[len]<a[i]){
		ans[++len]=a[i];
	}else{
		int j=lower_bound(ans+1,ans+len+1,a[i])-ans;
		ans[j]=a[i];
	}
}
1
2
3
4
5
6
7
8

最后，奉上完整代码：

#include
using namespace std;
const int N=1e7+5;
int ans[N],a[N],len,n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		if(ans[len]<a[i]){
			ans[++len]=a[i];
		}else{
			int j=lower_bound(ans+1,ans+len+1,a[i])-ans;
			ans[j]=a[i];
		}
	}
	cout<<len<<endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

OK，我们今天就讲到这里，咱们下篇博文再见