欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

51nod 1134 最长递增子序列

程序员文章站 2024-02-24 23:42:16
...

1134 最长递增子序列

给出长度为N的数组,找出这个数组的最长递增子序列。(递增子序列是指,子序列的元素是递增的)
例如:5 1 6 8 2 4 5 10,最长递增子序列是1 2 4 5 10。
输入
第1行:1个数N,N为序列的长度(2 <= N <= 50000)
第2 - N + 1行:每行1个数,对应序列的元素(-10^9 <= S[i] <= 10^9)
输出
输出最长递增子序列的长度。
输入样例

8
5
1
6
8
2
4
5
10

输出样例

5

思路来源于→这里
思路: 我把上边样例模拟一遍,简单的描诉一下自己的思路。

         初始一个 b 数组。 b[1] = a[1] ( a 数组 储存着原数列)。

         第i次更新就是更新 a[i],找到已存在的递增数列中第一个 >= a[i]  的值, 用 a[i] 代替它。

         如果没有大于 a[i] 的值, 那么最长递增序列的长度应该 加 1。

         第1次更新: 5  (原数列第一次更新只有一个数)

         第2次更新: 1

         第3次更新: 1 6

         第4次更新: 1 6 8

         第5次更新: 1 2 8

         第6次更新: 1 2 4
         
         第7次更新: 1 2 4 5
         
         第8次更新: 1 2 4 5 10

Code:

#include<bits/stdc++.h>

using namespace std;
const int N=1e5;
int a[N],b[N];

int q(int a,int c,int x)
{
	int mid,w=c;
	while(a<c)
	{
		mid=(a+c)/2;
		if(b[mid]<x)a=mid+1;
		else if(b[mid]==x) return mid;
		else c=mid;
	}
	return c;
 } 
int main()
{
	int n;
	cin>>n;
	if(n==1)
	{
		puts("1");
		return 0;
	}
	for(int i=1;i<=n;i++)cin>>a[i];
	b[1]=a[1];
	int k=2;
	for(int i=2;i<=n;i++)
	{
		if(a[i]>b[k-1])b[k++]=a[i];
		else {
			int p=q(1,k,a[i]);
			b[p]=a[i];
		}
	}
	k--;
	cout<<k<<endl;
	return 0;
}

Code:

#include<bits/stdc++.h>

using namespace std;
const int N=1e5;
int a[N],b[N];

int q(int a,int c,int x)
{
	int mid,w=c;
	while(a<c)
	{
		mid=(a+c)/2;
		if(b[mid]<x)a=mid+1;
		else {
			c=mid;
			w=c;
		}
	}
	return w;
 } 
int main()
{
	int n;
	cin>>n;
	if(n==1)
	{
		puts("1");
		return 0;
	}
	for(int i=1;i<=n;i++)cin>>a[i];
	b[1]=a[1];
	int k=2;
	for(int i=2;i<=n;i++)
	{
		if(a[i]>b[k-1])b[k++]=a[i];
		else {
			int p=q(1,k-1,a[i]);
			b[p]=a[i];
		}
	}
	k--;
	cout<<k<<endl;
	return 0;
}