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

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); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【动态规划】求最长不下降序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。