动态规划最长不下降序列

vlambda
2020-04-24

动态规划最长不下降序列

继续动态规划

题目

一个正整数序列b1，b2，…，bn，若下标为i1<i2<…<ik且有bi1<=bi2<=…<=bik，则称存在一个长度为k的不下降序列。可能有多个不下降序列，输出最长序列的长度。

解析

这道题

也是动态规划的题目

和以前

发布的那道

万达广场

有一些相似

这道题的精髓

就在于

从第2个到第n个

都要选择前面符合条件的数字中最大的一个

再+1

这道题

非常简单

没啥么好说的

下面是代码

加油！

大家最爱的代码

#include<bits/stdc++.h>

#include<iostream>

#include<cstdlib>

#include<cstdio>

using namespace std;

int n,a[1001],b[1001],maxx=0;

int main()

{

cin>>n;

for(int i=1;i<=n;i++)

{

cin>>a[i];

b[i]=1;

}

for(int i=2;i<=n;i++)

{

maxx=0;

for(int j=1;j<=i-1;j++)

{

if(a[j]<=a[i]&&b[j]>maxx)

maxx=b[j];

}

b[i]=maxx+1;

}

maxx=0;

for(int i=1;i<=n;i++)

{

if(b[i]>maxx)

maxx=b[i];

}

cout<<maxx<<endl;

return 0;

}

加油！

萌二宝来了

加油

往期精彩推荐

本文合肥一六八中学校园图片

来自老爸学校的张尚镯伯伯

在此表示感谢

欢迎关注

亮星的信息学小屋

觉得有用，请点右下方“在看”，谢谢鼓励

vlambda博客
学习文章列表