一、概念明确

先来看一串数字：(20,17,19,22,4,7,10,12,5,2,13)

  

1.序列：像以上排成一列的数字，我们叫它序列，其中每个数字，可以被称为一个元素。

2.子序列：将序列中的部分元素或者全部元素取出后构成的一个新序列，我们称为子序列。

例：将元素  17,22,6,7 取出来构成一个新序列 (17,22,6,7)，那么它就是一个子序列

注意：子序列是有序的，不能将后面的元素写在前面。比如写成(22,17,6,7)这种。

3.不下降子序列：不下降的意思是上升或者相同。

例：将元素 17,19,22取出来构成一个新序列 (17,19,22)，这个序列中的每个元素均大于或等于前一个元素，22大于19,19大于17，因此，我们称这个序列为不下降子序列。再如将元素6,7,10,12,13取出来构成一个新序列(6,7,10,12,13)，此序列符合不下降子序列的定义，因此它也是一个不下降子序列

4.最长不下降子序列： 子序列有很多，求出最长不下降子序列的意思是要求出一个子序列，它是不下降的，并且它在所有不下降的子序列中元素最多，这个最长不下降子序列可能有多个。

例：将元素6,7,10,12,13取出来构成一个新序列(6,7,10,12,13)，此时它就是一个最长不下降子序列，长度为5。虽然(10,12,13)、(17,19,22)、(2,13)、(5,13)等等都是不下降子序列，但是它们的长度都不是最长的，因此不能称为最长不下降子序列。

 二、解题方法

可以利用动态规划进行解题。在利用动态规划进行解题的时候，可以进一步划分为两种思路，分别是从前往后推理和从后往前推理。这两种思路都能够求出最长不下降子序列。

1.从前往后推理：依序求出以原序列中各元素分别为子序列结尾情况下能得出的最长不下降子序列

例子：以序列 (11,15,12,13,5,2)为例，通过从前往后推理求出最长不下降子序列的长度

 

 以1号元素为子序列的结尾：此时最长不下降子序列长度为1，因为只有1号元素本身(11)

 以2号元素为子序列的结尾：此时最长不下降子序列长度为2，此时包含1号元素和2号元素(11,15)

 以3号元素为子序列的结尾：此时最长不下降子序列长度为2，此时包含1号元素和3号元素(11,12)

 以4号元素为子序列的结尾：此时最长不下降子序列长度为3，此时包含1、3、4号元素(11,12,13)

 以5号元素为子序列的结尾：此时最长不下降子序列长度为1，此时包含5号元素本身(5)

 以6号元素为子序列的结尾：此时最长不下降子序列长度为1，此时包含6号元素本身(2)

如下图所示：

---

2.从后往前推理：依序求出以原序列中各元素分别为子序列起点情况下能得出的最长不下降子序列

  以6号元素为子序列的起点：此时最长不下降子序列长度为1，因为只有6号元素本身(2)

  以5号元素为子序列的起点：因为以5为起点，后面没有大于等于它的数字，此时最长不下降子序列长度为1，因为只有5号元素本身(5)

  以4号元素为子序列的起点：因为以13为起点，后面没有大于等于它的数字，此时最长不下降子序列长度为1，因为只有4号元素本身(13)

  以3号元素为子序列的起点：此时最长不下降子序列长度为2，此时包含3、4号元素(12,13)

  以2号元素为子序列的起点：此时最长不下降子序列长度为1，后面没有大于等于它的数字，此时最长不下降子序列长度为1，因为只有2号元素本身(15)

  以1号元素为子序列的起点：此时最长不下降子序列长度为3，此时包含1、3、4号元素(11,12,13)

---

3.总结：不管是从前往后推理，还是从后往前推理，都能够求出最长不下降的子序列的长度，其实动态规划就是一个填表的过程，上一个阶段的结果作为求下一个阶段求解的依据。针对这道题目，当我们求出以每个元素为起点或者终点的最长不下降子序列的长度之后，我们还需要找出整个长度行中的最大值，才能找到整个序列的最长不下降子序列长度。

三、代码解题

利用动态规划进行解题，需要找出3个必备条件。

1. 确定状态
2. 确定边界
3. 确定状态转移方程

A.代码1（从前往后推理）

数据结构：

    int f[1005];  f[i] 代表以第i号元素为终点最长不下降子序列的长度（确定状态）

    int mx = -1; mx用来存放最终最长不下降子序列的长度大小

    int data[1005]; data数组用来存放序列数字

输入序列数据和确定边界：

	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i]=1;  //确定边界
	}

 其中 ，f[i]数组中的每个元素都需要初始化为1(确定边界)，并不是只有f[1]需要初始化为1，其它元素都需要。为什么呢？假设我们只初始化f[1]=1，其它元素不初始化为1，以序列 (11,15,12,13,5,6)为例：

 通过观察发现，本来在6号元素位置的长度f[6]应该为2，但是因为没有对f[i]每个元素初始化为1，使得f[6]=1，与我们的期望不符合

核心代码(状态转移方程)：

	for(int i=2;i<=n;i++)
	{
		for(int j=i-1;j>=1;j--)
		{
			if(a[i]>=a[j])
				f[i]=max(f[i],f[j]+1);
		}
	}

找出f[i[中的最大值，求出最长不下降子序列的长度 

	for(int i=1;i<=n;i++)
	{
		mx=max(mx,f[i]);
	}

完整代码 

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[1001];
int f[1001]; 
int mx = -1; 
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i]=1; 
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=i-1;j>=1;j--)
		{
			if(a[i]>=a[j])
				f[i]=max(f[i],f[j]+1);
		}
	}
	for(int i=1;i<=n;i++)
	{
		mx=max(mx,f[i]);
	}
	printf("%d",mx);
	return 0;
}

B.代码2（从后往前推理） 

 数据结构：

    int f[1005];  f[i] 代表以第i号元素为起点最长不下降子序列的长度（确定状态）

    int mx = -1; mx用来存放最终最长不下降子序列的长度大小

    int data[1005]; data数组用来存放序列数字

输入序列数据和确定边界：

	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i]=1;  //确定边界
	}

  其中 ，f[i]数组中的每个元素都需要初始化为1(确定边界)，并不是只有f[n]需要初始化为1，其它元素都需要。为什么呢？假设我们只初始化f[n]=1，其它元素不初始化为1，以序列 (11,15,12,13,5,6)为例：

  通过观察发现，本来在3号元素位置的长度f[3]应该为2，在1号元素位置的长度f[1]应该为3，但是因为没有对f[i]每个元素初始化为1，使得f[3]=1，f[1]=2，与我们的期望不符合

 核心代码(状态转移方程)：

	for(int i=n-1;i>=1;i--)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]<=a[j])
			{
				f[i]=max(f[i],f[j]+1);
			}
		}
	}

找出f[i[中的最大值，求出最长不下降子序列的长度 

	for(int i=1;i<=n;i++)
	{
		mx=max(mx,f[i]);
	}

 完整代码 

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[1001];
int f[1001]; //以第i项为起点的最长不下降子序列的长度
int mx = -1; 
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i]=1; 
	}
	for(int i=n-1;i>=1;i--)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]<=a[j])
			{
				f[i]=max(f[i],f[j]+1);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		mx=max(mx,f[i]);
	}
	printf("%d",mx);
	return 0;
}

四、在线oj测试

写好代码之后，如何验证你写的是否正确呢？可以登录这个OJ，来测试代码的正确性

http://ybt.ssoier.cn:8088/problem_show.php?pid=1281

需要注意的是，该题求的是最长上升子序列，和最长不下降子序列还是有区别的需要稍微修改一下核心代码，上升子序列要求子序列中的元素不可以相同，而最长不下降子序列中的元素可以相同

可以做如下修改：

	//从前往后退
    for(int i=2;i<=n;i++)
	{
		for(int j=i-1;j>=1;j--)
		{
			if(a[i]>a[j])
				f[i]=max(f[i],f[j]+1);
		}
	}


    //从后往前推
	for(int i=n-1;i>=1;i--)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]<a[j])
			{
				f[i]=max(f[i],f[j]+1);
			}
		}
	}

五、提高拓展

以上只是求出的最长不下降子序列的长度，并没有输出最长不下降子序列中的各个元素，可以花点时间去思考一下怎么才能输出最长不下降子序列中的各个元素?。今天的题解就到这里啦 ！如果有任何问题欢迎添加博主微信：Q1313135互相讨论学习。我们下期再见~~~

 

   

• 状态设计：dp[i]表示以str[i]结尾的最长不下降子序列长度
•     状态转移方程：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）；
•     当然，后面我们还可以输出这个最长不下降子序列的内容，只需要从后面开始枚举dp的值进行递减，只要dp的值与temp(最长子序列长度递减)相等， 就把str[i]的值加到lis中，直到temp==0为止。
•     输出第一个最长不下降子序列的内容呢：不过是从前面开始枚举罢了。

/**
    2)状态设计：dp[i]表示以str[i]结尾的最长不下降子序列长度
    状态转移方程：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）；
    当然，后面我们还可以输出这个最长不下降子序列的内容，只需要从后面
    开始枚举dp的值进行递减，只要dp的值与temp(最长子序列长度递减)相等，
    就把str[i]的值加到lis中，直到temp==0为止。
    输出第一个最长不下降子序列的内容呢：不过是从前面开始枚举罢了。
*/

/**
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    cout << "input a string:\n";
    cin >> str;
    int len=str.size();
    int dp[len],ans=0;  //dp[i]表示以str[i]结尾的最长不下降子序列长度
    dp[0]=1;            //状态转移方程：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）

    for(int i=1;i<len;++i)
    {
        dp[i]=1;
        for(int j=0;j<i;++j)
        {
            if(str[j]<=str[i]&&dp[j]+1>dp[i])
                dp[i]=dp[j]+1;
        }
        ans=max(ans,dp[i]);
    }
    string lis; //lis输出最长不下降子序列
    int temp=ans;
    for(int i=len-1;i>=0;--i)
    {
        if(dp[i]==temp)
        {
            lis=str[i]+lis;   temp从后开始往前寻找结果，当最长不下降序列
            --temp;           不止一个结果时，得到的序列是最后一组
        }
    }
    cout << ans << endl;
    for(auto a:str)
        cout << a << ' ';
    cout <<  endl;
    for(auto a:dp)
        cout << a << ' ';
    cout << endl;
    cout << lis << endl;
    string first;
    temp=1;
    for(int i=0;i<len;++i)
    {
        if(dp[i]==temp)
        {
            first+=str[i];
            ++temp;
        }
    }

    cout << "first substr:\n";
    cout << first << endl;
    return 0;
}
*/

3)为了后续不下降子序列的内容进行输出，也可开一个result数组，result[i]
    表示str[i]的前继结点，一个序列的首结点设置为-1，与其他节点进行区分，
    其实和第一个程序利用dp的值进行输出内容是一样的。

/**
    3)为了后续不下降子序列的内容进行输出，也可开一个result数组，result[i]
    表示str[i]的前继结点，一个序列的首结点设置为-1，与其他节点进行区分，
    其实和第一个程序利用dp的值进行输出内容是一样的
*/

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    cout << "input a string:\n";
    cin >> str;
    int len=str.size();
    int dp[len];        //dp[i]表示以str[i]结尾的最长不下降子序列长度
    dp[0]=1;            //状态转移方程：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）
    int result[len];    //result[i]表示str[i]的前继结点
    result[0]=-1;       //一个序列的首结点设置为-1，与其他节点进行区分
    for(int i=1;i<len;++i)
    {
        dp[i]=1;
        result[i]=-1;
        for(int j=0;j<i;++j)
        {
            if(str[j]<=str[i]&&dp[j]+1>dp[i])
            {
                dp[i]=dp[j]+1;
                result[i]=j;
            }
        }
    }
    int p=0,imax=0;
    for(int i=0;i<len;++i)
    {
        if(dp[i]>imax)
        {
            imax=dp[i];
            p=i;
        }
    }
    string lis;
    for(;p!=-1;)
    {
        lis=str[p]+lis;
        p=result[p];
    }
    cout << imax << endl;
    cout << lis << endl;
    cout << "调试:\n";
    for(auto a:str)
        cout << a << ' ';
    cout <<  endl;
    for(auto a:dp)
        cout << a << ' ';
    cout << endl;
    for(auto a:result)
        cout << a << ' ';
    cout << endl;
    return 0;
}

$$求最长不下降序列$$

Description

设有n(n<=1000)个不相同的整数(小于32767)组成的数列，记为：

a1,a2,…,an,其中任意两个数不相同。

例如：3,18,7,14,10,12,23,41,16,24。

若有 且有 。则称为长度为e的不下降序列。如上例中，3,18,23,24为一个长度为4的不下降序列，同时也有3,7,10,12,16,24长度为6的不下降序列。程序要求，当原始数列给出后，求出最长的不下降数列的长度。

Sample Input

10

3 18 7 14 10 12 23 41 16 24

Sample Output

6

解题思路

用两个循环来枚举到哪个个数的最长不下降序列和这个数可能连接到的不下降序列。

#include<cstdio>
#include<iostream>
using namespace std;
int num,n,a[1001],sum[1001];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	  {
	  	scanf("%d",&a[i]);
	  	sum[i]=1;
	  	for (int j=1;j<i;j++)
	  	  if (a[j]<a[i]&&sum[j]>=sum[i])//如果a[j]比a[i]小并且第j个数的不下降序列比当前的长或相等
	  	    sum[i]=sum[j]+1;
	  	num=max(num,sum[i]);//判断当前段是否为最优
	  }
	printf("%d",num);
}