本文共 510 字，大约阅读时间需要 1 分钟。

题目描述

这是一个经典的LIS(即最长上升子序列)问题，请设计一个尽量优的解法求出序列的最长上升子序列的长度。给定一个序列A及它的长度n，请返回LIS的长度。

求解过程

给定一个数组A,以及他的长度N生成长度为N的数组dpdp[i]的含义为：必须以A[i]结尾时的最长递增子序列的长度.显然 dp[0]=1;对于i 为1-N-1时, dp[i]为比A[i]小的数结尾的最长的子序列的长度+1状态转移方程为     dp[i] = max{dp[j]+1|0<=j
   

代码实现

class LongestIncreasingSubsequence{public:    int getLIS(vector
   
     A, int n)     {        if(!n)            return 0;        int *dp = new int[n];        dp[0]=1;        int maxlongs = 1;        for (int i=1; i
    
     =0; --j)             {                if(A[j]
    
   

转载地址：http://gehji.baihongyu.com/