【题目描述】

设有由n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j)，若存在i1<i2<i3<…<ie 且有b(i1)<b(i2)<…<b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列的长度。

例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。

例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63组成的长度为8的不下降序列。

【输入描述】

第一行为n,第二行为用空格隔开的n个整数。

【输出描述】

第一行为输出最大个数max

【样例输入1】

14  13 7 9 16 38 24 37 18 44 19 21 22 63 15

【样例输出1】

max=8

【样例输入2】

7  1 7 3 5 9 4 8

【样例输出2】

max=4

【题目分析】

• 一维数组dp问题。

• 我们采用'从前往后'推理的方式进行分析。依序求出以原序列中各元素分别为子序列结尾情况下能得出的最长不下降子序列。我们先给上面的数字的一部分进行分析（为了后面分析方便，我们给数字加入编号）

  
  
  

  
  
  

• 数字	13	7	9	16	38	24	37	18
  编号	1	2	3	4	5	6	7	8

  （1）以编号为1的子序列作为结尾，那么只包含1号元素本身。最长长度：1

  （2）以编号为2的子序列作为结尾，那么也只能包含2号元素本身。最长长度：1

  （3）以编号为3的子序列作为结尾，那么包含2号和3号（7，9）。最长长度：2

  （4）以编号为4的子序列作为结尾，那么包含2，3，4号（7，9，16）。最长长度：3

  （5）以编号为5的子序列作为结尾，那么包含2，3，4，5号（7，9，16，38）。最长长度：4

    (6)  以编号为6的子序列作为结尾，那么包含2，3，4，6号（7，9，16，24）。最长长度：4

  （7）以编号为7的子序列作为结尾，那么包含2，3，4，6，7号（7，9，16，24，37）。最长长度：5

  （8）以编号为8的子序列作为结尾，那么包含2，3，4，8（7，9，16，18）号。最长长度：4

那么我们可以把上面的表格扩展成下面这个样子：

从表格中可以看出，最长长度是5。那么这个最长长度是如何分析出来的呢？

其实从上面的过程中就可以看出，每个元素的长度都是经过比较得出来的。

一开始，所有的数字编号的长度都为1(每个元素都算是一个长度)。我们用dp数组保存，那么就是dp[i]=1。

然后开始比较和筛选的过程。

那么比较的是什么？比较的是数字的大小。也就是要大于等于前者，这个时候才要进行判断，是否更改当前编号的长度，如果不更换就是dp[i]不变。那么基本框架如下：

//外循环表示我们以每一个数都作为子序列结尾进行求解   for(int i=1; i<=n; i++) {  	dp[i]=1;  //用dp数组表示每个数字的长度，一开始每个数字都是1  (注意：不一定要全部初始化为1，只要能正确表示后续长度即可)  	  	//内循环到i-1终止，找出符合条件的数   	for(int j=1; j<i; j++) {  	      	}  }

那么内部循环里面实际上就分成两种情况。要不当前遍历的这个数dp[i]要么不变（dp[i]本身），要么是内循环中大于等于当前数的长度加1

那么什么时候需要进行dp数组长度的更新呢，可以从上面的表格中看出。当后者比前者大时，需要判断和更新。

也就是下面这样：

//外循环表示我们以每一个数都作为子序列结尾进行求解   for(int i=1; i<=n; i++) {  	dp[i]=1;  //用dp数组表示每个数字的长度，一开始每个数字都是1  	  	//内循环到i-1终止，找出符合条件的数   	for(int j=1; j<i; j++) {  		  		//因为j最大是i-1, 所以是a[i]>=a[j]   		if(a[i]>=a[j]){  			//如果后者比前者大，那么考虑更新当前值dp[i]   		}   	}  }

那么就可以得出结论，dp[i]的值，要么跟dp[i]相等，要么是dp[j]+1。

比如我们在分析6号元素时，此时外循环a[6]=24, 内循环a[j]从13一直到38。  但是当j=1，2，3，4时，满足条件a[i]>=a[j], 那么dp[i]就会被不断的更新。  j=1时，d[j]=1, d[j]+1=2, 取d[j]+1  j=2时，d[j]=1, d[j]+1=2, 取d[j]+1  j=3时，d[j]=2, d[j]+1=3, 取d[j]+1  j=4时，d[j]=3, d[j]+1=4, 取d[j]+1

 可以看出，我们并没有取到过d[j]，其实很简单，我们把a[5]=38改成a[5]=24,

那么在比较的过程中就可以得到

i=5  j=4  a[5]>=a[4] 不成立  此时 dp[i]=1,d[j]+1=5, 此时取d[i]

总结：

//外循环表示我们以每一个数都作为子序列结尾进行求解   for(int i=1; i<=n; i++) {  	dp[i]=1;  //用dp数组表示每个数字的长度，一开始每个数字都是1  	  	//内循环到i-1终止，找出符合条件的数   	for(int j=1; j<i; j++) {  		  		//因为j最大是i-1, 所以是a[i]>=a[j]   		if(a[i]>=a[j]){  			//如果后者比前者大，那么考虑更新当前值dp[i]   			dp[i]=max(dp[i],dp[j]+1)   		}   	}  }

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

【参考代码】

#include<bits/stdc++.h>   using namespace std;  int a[1005],dp[1005];  int main()  {      int n;      int maxx=-9999;      cin>>n;      for(int i=1;i<=n;i++)          cin>>a[i];      for(int i=1;i<=n;i++)      {          dp[i]=1;          for(int j=1;j<i;j++)              if(a[j]<=a[i]){              	dp[i]=max(dp[i],dp[j]+1);  			}          if(dp[i]>maxx)          {              maxx=dp[i];          }      }      cout<<"max="<<maxx<<endl;       return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});