最长递增子序列

8
5
1
6
8
2
4
5
10

5

#include <stdio.h>
#include <iostream>
using namespace std;
int main( )
{
	int a[50005]  , res[50005];
	int n , max = -99999 , tail = 0;
	cin >> n;
	for(int i = 0 ; i < n ; i++)
	{
		scanf("%d" , &a[i]);
	}
	for(int i = 0 ; i < n ; i++)
	{
		if(a[i] > max)
		{
			res[tail++] = a[i];
			max =res[tail - 1];
		}
		else
		{
			for(int j = 0 ; j < tail ; j++)
			{
				if(a[i] <= res[j])
				{
					res[j] = a[i];
					break;
				}
			}
			max = res[tail-1];
		}
		
	}
	printf("%d\n", tail);
	return 0;
}
//5 1 6 8 2 4 5 10
//1.开一个res[]数组存取满足要求的数字 用max 标记数组中最大的数，
//遍历该数 ， 如果小于 res[] 则互换 ， 保证max 为res[]中末尾最大的数 

2.将该数组升排序 ，再与原数组lcs;

(超时）

#include <stdio.h>
#include <iostream>
using namespace std;
#include <algorithm>
int dp[5000][5000];
int main()
{
	int n , a[5005] , b[5005];
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; i++)
	{
		scanf("%d" , &a[i]);
		b[i] = a[i];
	}
	sort(a+1 , a+n+1);
//	for(int i = 0 ; i < n ; i++)
//	{
//		printf("a[i] = %d  " , a[i]);
//		printf("b[i] = %d  " , b[i]);
//	}
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= n ; j++)
		{
			if(b[i] == a[j])
			{
				dp[i][j] = dp[i-1][j-1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
			}
		}
	}
//	for(int i = 1 ; i <= n ; i++)
//	{
//		for(int j = 1 ; j <= n ; j++)
//		{
//			printf("%d " , dp[i][j]);
//		}
//		printf("\n");
//	}
	printf("%d\n" ,dp[n][n]);
	return 0;
}