最长单调递增子序列——动态规划

#include

#include

#include

#include

using namespace std;

#define MAXN 10000

int dp[MAXN];//意思是：第i个必选，那么前i中的最长单调递增子序列的长度

int n;

int a[MAXN];

int main()//最长单调递增子序列

{

int maxx = 0;

cin>>n;

for(int i = 1; i <= n; i++)

cin>>a[i];

memset(dp,0,sizeof(dp));

dp[1] = 1;

for(int i = 1; i <= n ; i++)

{

for(int j = 1; j < i; j++)

{

if(a[j] < a[i]) dp[i] = max(dp[i],dp[j] + 1);

}

}

for(int i = 1; i <= n; i++)

{

if(maxx < dp[i]) maxx = dp[i];

}

cout<<maxx<<endl;

return 0;

}