最长不下降子序列

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

分析：此题如若采用暴力的方法来解答，即对于每个元素有取或是不取两种选择，时间复杂度可以达到O(2^n)。

令dp[i]表示以A[i]结尾的最长不下降子序列长度(和最大连续子序列和问题一样，以A[i]结尾是强制的要求)。此时会有两种情况：一种是存在A[i]之前的元素Aj，使得A[j]<=A[i]且dp[j]+1>dpi,那么就把A[i]跟在以A[j]结尾的LIS后面，形成一条更长的不下降子序列(dp[i]=dp[j]+1)；另一种是A[i]之前的元素都比A[i]大，那么A[i]就只好自己形成一条LIS，此时的长度为1。则其状态转移方程为：dp[i]=max(1,dp[j]+1)(j=1,2,…,i-1&&A[j]<A[i])，其边界条件就为：dp[i]=1(1<=i<=n)。其整体复杂度为O(n^2)。

#include<iostream>
#include<algorithm>
#include<stdlib.h>
using namespace std;

const int N=100;
int A[N],dp[N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>A[i];
    }
    int num=-1;
    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;
            }
        }
        num=max(num,dp[i]);
    }
    cout<<num;
    system("pause");
    return 0;
}