作为一个菜鸟，本文作为查询模板
【问题1】最长递增子序列问题
【问题描述】设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<ak1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
采用一个数组temp[]保存 以当前元素结尾的最长递增子序列长度，最后求出全局最优解
更新最长递增子序列的条件：a[i]>a[j] (i>j) 且前一个递增序列长度大于等于当前递增序列长度
动态规划：
代码（不重复的子序列）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<iostream> #define MAX 100 using namespace std; int main() { int num[MAX],temp[MAX]; int i,j,n,maxl,m; while(cin>>n) { temp[0]=1; maxl=0; for(i=0;i<n;i++) cin>>num[i]; for(i=1;i<n;i++) { m=0; for(j=0;j<i;j++) { if(num[i]>num[j]&&temp[j]>m) m=temp[j]; } temp[i]=m+1; if(temp[i]>maxl) maxl=temp[i]; } cout<<maxl<<endl; } } |
几个解释得较好的链接，供学习用：
