最长递增子序列之我的第一个动态规划
求(严格)最长递增子序列
我在仔细参考了知乎作者王勐,徐凯强Andy的文章(http://www.zhihu.com/question/23995189/answer/35429905)之后,冒着大无畏的探索精神,成功写出人生中的第一个动态规划(中间没有看其他任何代码喔!),欧耶!此刻我的心情万分激动,体内的多巴胺在急剧分泌。。。
完整代码如下:
//最长递增子序列,动态规划,数组下标从1开始
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
cout<<endl;
int *p=new int[n+1]; //输入的原始数据,第一个数据为p[1]
p[0]=0;
for(int i=1;i<=n;i++){
cin>>p[i];
}
//算法核心
int *len=new int[n];
len[0]=0;
len[1]=1;
int k=1;
int book[50][50]={0};
book[1][1]=p[1];
for(int i=2;i<=n;i++){
int add=0;
int au=k;
for(int j=1;j<=k;j++){ //k为递增子序列的段数,book[i][]存储递增子序列的元素,len[i]存储递增子序列的长度
if(p[i]>book[j][len[j]]){ //大于最大值
len[j]=len[j]+1;
book[j][len[j]]=p[i];
continue;
}
else if(p[i]<book[j][1]) add++;
else if(p[i]<book[j][len[j]]){ // 介于头和尾之间 ,创建新的子序列
k++;
int t=1;
while(p[i]>book[j][t]){
book[k][t]=book[j][t];
t++;
}
book[k][t]=p[i];
len[k]=t;
continue;
}
}
if(add==au){
k++;
book[k][1]=p[i];
len[k]=1;
}
}
//输出最长子序列
int max=len[1];
int mark=1;
int best[10]={0}; //假设相同最长子序列段数小于10
int num=1; //表示最长子序列的段数
for(int j=1;j<k;j++){ //寻找len[]中的最大值
if(max<len[j+1]){
max=len[j+1];
mark=j+1;
}
}
//找出相同的最长子序列
best[1]=mark;
for(int j=1;j<=k;j++){
if((max==len[j])&&(mark!=j)){
num++;
best[num]=j;
}
}
int position=best[1];
for(int j=1;j<=num;j++){
position=best[j];
for(int i=1;i<=len[position];i++)
{
cout<<book[position][i]<<" ";
}
cout<<endl;
}
delete p;
delete len;
return 0;
}
(额。。。统计结果的时候可能多余了,这无关紧要!)