求最长上升子序列用动态规划

比如输入

7

1 7 3 5 9 4 8

输出

4

他的最长上升子序列为：1 3 5 8

采用动态规划一般步骤

先找出子问题

对子问题分别求解

定义一个动态数组存放子问题的解

#include<iostream> #include<cmath> #include<cstring> #include<algorithm> using namespace std;int a[1010],maxlen[1010]; int main() { int n,maxs=0; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; maxlen[i]=1; } for(int i=2;i<=n;i++) {//先令第一个为1，然后求第i个数为终点的最长上升序列长度 for(int j=1;j<=i;j++) { if(a[i]>a[j])//只要有比前面大的，就判断是否最后一个比前面要大 maxlen[i]=max(maxlen[i],maxlen[j]+1); } } for(int i=1;i<=n;i++) { if(maxlen[i]>maxs)maxs=maxlen[i]; //找出数组里最大的就是最长上升子序列 } cout<<maxs; /* 另外求数组的最大值除了用上面我写的这种最容易想到的方法还可以直接调用函数，大神的代码为啥那么短，就是会这些所以上面三行可以直接写成cout<<*max_element(maxlen+1,maxlen+n+1);*/return 0;}