135. 最长上升子序列 nlogn dp

itdef / 2024-09-25 / 原文

// 103 最长上升子序列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


/*
http://oj.daimayuan.top/course/5/problem/135

给定一个长度为 n的数组 a1,a2,…,an
，问其中的最长上升子序列的长度。也就是说，我们要找到最大的 m以及数组 p1,p2,…,pm
，满足 1≤p1<p2<⋯<pm≤n并且 ap1<ap2<⋯<apm。

输入格式
第一行一个数字 n。

接下来一行 n个整数 a1,a2,…,an。

输出格式
一个数，表示答案。

样例输入
6
3 7 4 2 6 8

6
1 2 3 4 5 6

6
6 5 4 3 2 1

样例输出
4
数据规模
对于所有数据，保证 1≤n≤1000,1≤ai≤109。
*/
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


const int N = 1010;
int a[N];
int dp[N];
int n;
int len;


void find(int x) {
	int l = 1; int r = l + len ;
	while (l < r) {
		int mid = (l+r) >> 1;
		if (dp[mid] >= x)
			r = mid;
		else 
			l = mid + 1;
	}

	if (dp[l] == 0x3f3f3f3f) len++;
	dp[l] = x;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	memset(dp, 0x3f, sizeof dp);
	for (int i = 1; i <= n; i++) {
		int curr = a[i];
		find(curr);
	}

	cout << len << endl;

	return 0;
}

// 103 最长上升子序列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


/*
http://oj.daimayuan.top/course/5/problem/135

给定一个长度为 n的数组 a1,a2,…,an
，问其中的最长上升子序列的长度。也就是说，我们要找到最大的 m以及数组 p1,p2,…,pm
，满足 1≤p1<p2<⋯<pm≤n并且 ap1<ap2<⋯<apm。

输入格式
第一行一个数字 n。

接下来一行 n个整数 a1,a2,…,an。

输出格式
一个数，表示答案。

样例输入
6
3 7 4 2 6 8

6
1 2 3 4 5 6

6
6 5 4 3 2 1

样例输出
4
数据规模
对于所有数据，保证 1≤n≤1000,1≤ai≤109。
*/
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


const int N = 1010;
int a[N];
int dp[N];
int n;

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

	cout << ans << endl;

	return 0;
}