动态规划-最长不下降子序列(LIS)

动态规划-最长不下降子序列(LIS)

1. 题目描述

   在一个数字序列中，找到一个最长的子序列(可以不连续)，使得这个子序列是不下降(非递减)的。

   例如，现有序列A = {1,2,3,-1,-2,7,9}（下标从1开始），它的最长不下降子序列是{1,2,3,7,9},长度为5。另外，还有一些子序列是不下降子序列，比如{1,2,3}，{-2,7,9}等，但都不是最长的。

   

2. 令dp[i]表示以A[i]结尾的最长不下降子序列长度(和最大连续子序列和问题一样,以A[i]结尾是强制的要求)。这样对A[i]来说就会有两种可能：

   1. 如果存在A[i]之前的元素A[j] (j < i)，使得A[j] <= A[i]且dp[j] + 1 > dp[i] （即把A[i]跟在以A[j]结尾的LIS后面时能比当前以A[i]结尾的LIS长度更长），那么就把A[i]跟在以A[j]结尾的LIS后面，形成一条更长的不下降子序列 (令dp[i] = dp[j] + 1)

   2. 如果A[i]之前的元素都比A[i]大，那么A[i]就只好自己形成一条LIS,但是长度为1,即这个子序列里面只有一个A[i]。

      最后以A[i]结尾的LIS长度就是1,2中能形成的最大长度。

3. 状态转移方程

   由此可以写出状态转移方程：dp[i] = max{1,dp[j]+1} (j = 1,2,…,i-1 && A[j] < A[i])

   上面的状态转移方程中隐含了边界：dp[i] = i(1 <= i <= n)。显然dp[i]只与小于i的j有关，因此只要让i从小到大遍历即可求出整个dp数组。由于dp[i]表示的是以A[i]结尾的LIS长度，因此从整个dp数组中找出最大的那个才是要寻求的整个序列的LIS长度，整体复杂度为O(n^2)。

   因此就可以想象究竟重复计算出现在哪里了：每次碰到子问题”以A[i]结尾的最长不下降子序列“时，都去重新遍历所有子序列，而不是直接记录这个子问题的结果。

4. 代码如下：

   #include <iostream>
   #include <cstdio>
   #include <algorithm>
   
   using namespace std;
   
   const int N = 100;
   int A[N],dp[N];
   int main(){
       int n
       scanf("%d",&n);
       for(int i = 1 ; i <= n ; i++){
           scanf("%d",&A[i]);
       }
       int ans = -1;	// 记录最大的dp[i]
       for(int i = 1 ; i <= n ; i++){
           dp[i] = 1;	// 边界初始条件(即先假设每个元素自成一个子序列)
           for(int j = 1 ; j < i ; j++){
               if(A[i] >= A[j] && (dp[j] + 1 > dp[i])){
                   dp[i] = dp[j] + 1;	// 状态转移方程，用以更新dp[i]
               }
           }
           ans = max(ans,dp[i]);
       }
       printf("%d",ans);
       return 0;
   }
   

5. 运行结果