最长递增子序列

问题描述

求最长递增子序列的长度

分析

主要是确定状态，F[i]表示以ai 结束的最长递增子序列长度，F[i]=max{1,F[j]+1|aj<ai,j<i}

代码

#include<iostream>
#include<vector>
using namespace std;
int dp[100];
int main()
{
    int n;
    while(cin>>n)
    {
        vector<int> v;
        int num;
        for(int i=0;i<n;i++)
        {
            cin>>num;
            v.push_back(num);
        }
        dp[0]=1;
        for(int i=1;i<n;i++)
        {
            int Max=1;
            for(int j=0;j<i;j++)
            {
                if(v[i]>v[j]) Max =max(Max,dp[j]+1);//递增
            }
            dp[i]=Max;
        }
        int res=1;
        for(int i=0;i<n;i++)
        {
            res=max(res,dp[i]);
        }
        cout<<res<<endl;
    }
}