题目描述

有一个序列有N个数，A[1],A[2],A[3],……,A[N]，求出最长非降子序列长度。

我们首先我定义一个“状态”来代表它的子问题，并且找到它的解。一般情况下，某个状态只与它前面出现的状态有关，而独立于后面的状态。
假如我们考虑求A[1],A[2],A[3],………,A[i]的最长非降子序列的长度，其中i<N,那么这个问题就是原问题的一个子问题，然后我们定义d(i),表示前i个数中，以A[i]结尾的最长非降子序列的长度。只要我们把d(1)到d(N)都计算出来，那么答案就是这里面最大的那个。现在我们来求状态转移方程。
举一个例子，有如下序列

5,3,4,8,6,7

我们可以得到

• 前1个数的LIS长度d(1) = 1 （5）
• 前2个数的LIS长度d(2) = 1 （3）
• 前3个数的LIS长度d(3) = 2 （3,4 d(3) = d(2)+1）
• 前4个数的LIS长度d(4) = 3 ( 3,4,8 d(4) = max{d(1),d(2),d(3)}+1)

由上我们可以看出状态转移方程为d(i) = max{d[A[j]}+1 j<i && A[j]<=A[i]。

代码如下

vector<int> nums{5,3,4,8,6,7};
void LIS(vector<int>& nums) {      
        if (nums.empty()) return ;
        vector<int> dp;
        int len = nums.size();
        for (int i = 0;i < len;i++) {
            dp.push_back(1);
        }
        for (int i = 1;i<len;i++) {            
            for (int j=0;j<i;j++) {
                  if (nums[i]>=nums[j] && dp[j]+1>dp[i])
                      dp[i] = dp[j]+1;
            }
        }
        ostream_iterator<int> oo(cout," ");
        copy(dp.begin(),dp.end(),oo);
        return ;  
    }
结果为
1 1 2 3 3 4