47 星南二楼

动态规划，相当于求解最长子序列问题

#include <iostream>  

using namespace::std;
using std::cout;
using std::cin; 

int n;
int a[5100],dp[5100];

int xnel(int n, int a[]) 
{
    int result = 0;
    for(int i=0; i<n; i++)
	{
        for(int j=0; j<i; j++)
		{
            if(a[j]<a[i])
			{
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
        result = max(result,dp[i]+1);
    }
    return result;
}
  
int main() 
{  
    cin >> n;
    for(int i=0; i<n; i++)
    {
    	cin >> a[i];
	}
	std::cout << xnel(n, a);
    return 0;  
}