【问题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) 且前一个递增序列长度大于等于当前递增序列长度
动态规划:
代码(不重复的子序列)
C++
#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;
}
}
几个解释得较好的链接,供学习用: