当前位置:   article > 正文

关于最长上升子序列的nlogn时间复杂度的DP算法详解(易懂)_最长上升子序列 nlogn

最长上升子序列 nlogn

受启发于:https://www.cnblogs.com/wxjor/p/5524447.html

在学习DP时相信我们都遇到过这一道题:最长上升子序列,这道题用DP来解的话时间复杂度为n^2;
这在n大概是10000,而时间限制为1秒时是可以被接受的,但是当n取到100000时我们就不能只用简单的DP来做了

这个时候我们可以使用另一种DP,那就是对长度DP

我们建立一个数组DP[100001];

DP[i]表示能使上升序列长度为i时的所有序列中的最右边的数字的最小值

比如序列 2 3 4 1 5 8 6,很显然,最长上升子序列长度为5,分别为 2 3 4 5 6或者 2 3 4 5 8

那么DP[1…5]={1 3 4 5 6}

因为长度为1时,我们可以取任意数当序列,所以很明显1是最小的,所以DP[1]=1。

当长度为2时,我们可以取的序列有 {2,3} {2,4} {2,5},{2,8}…等等,很明显所有序列中的最右边的数字的最小值为3,所以DP[2]=3;

依次类推

这个数列有什么用呢

如果我们已经有了这个DP数列,我得到了一个新数字我该怎么处理呢,比如10

很明显,如果它比6大,说明,我们可以得到序列 2 3 4 5 6 10,所以我们就可以将答案和DP数组的长度更新为6,同时DP[6]=10
既DP[1…6]={1 3 4 5 6 10}
依次类推

但是如果我们得到一个新数字不能比DP最右边的数字大呢,比如这个数字是2的时候, 我们该怎么办呢,

我们当然不能忽略这个数字,当它等于2的时候,我们可以知道,我们可以得到上升序列为{1 2},所以DP[2]应该等于2才对
所以我们就可以更新DP数列DP[1…6]={1 3 4 5 6 10},更新为DP[1…6]={1 2 4 5 6 10}

那有人会问,我们更新DP数列有什么用?
那是肯定有用啊 ,因为我们通过不断的更新以后,我们会把DP数组元素变得尽可能地小,导致我们可能会把最右边的数字更新得更小,使得增加长度更容易,这很棒不是吗?

比如说来了一个新的数字9的话,它比10小,那么我们就可以把10更新为9,既DP[1…6]={1 2 4 5 6 9}

增加的方法很容易,那我们的更新方法是什么?

最重要的来了:
最重要的来了:
最重要的来了:

我们更新DP数组的方法是从从到右找到第一个比他大的数字,然后把它替换掉

如果我们傻傻地从左往右找,时间复杂度仍然为n^2,欧,功亏一篑

一拍脑袋,既然DP数组是有序递增的,那么我们为什么不使用二分查找呢

所以,我们将上面的步骤用代码表示出来的时候是这样的:

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e6 + 1;
int dp[maxn];
int main() {
	int n,num,ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> num;
		if (i == 1 || num > dp[ans - 1]) { dp[ans] = num; ans++; }
		else {
			auto q = lower_bound(dp, dp + ans + 1,num);
			*q = num;
		}
	}
	cout << ans << endl;
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读