首页 > 代码库 > 最长非降/下降子序列问题(DP)（待续...）
最长非降/下降子序列问题(DP)（待续...）
注意：抽象成以下描述即为最长非降/下降子序列问题（一维状态）
问题描述：在一个无序的序列a1,a2,a3,a4…an里，找到一个最长的序列满足：（不要求连续）
ai<=aj<=ak…<=am,且i<j<k…<m.（最长非降子序列）
或 ai>aj>ak…>am,且i<j<k…<m.（最长下降子序列）。
问题分析：（以最长非降子序列为例）
考虑状态数组opt[maxn]; 其中opt[i]表示a[i]时可与之前元素构成非降子序列的最大长度；可参考模板（随个人喜好，不唯一）：
for(int i = 1; i <= n; i++) { scanf("%d", &array[i][0]); array[i][1] = 1; //初始化到a[i]为止最长子序列长度为1; } for(int i = 2; i <= n; i++) { int len = 0; for(int j = 1; j < i; j++) //a[i]前的最长子序列 { if(array[j][0] >= array[i][0] && array[j][1] > len) //注意此处的判断条件 { len = array[j][1];//更新最长最序列长度 } } if(len > 0) array[i][1] = len + 1;//记录并更新a[i]处最长子序列长度 }
1 for(int i = 1; i <= n; i++) 2 { 3 scanf("%d", &array[i]); 4 opt[i] = 1; //初始化到a[i]时的最长子序列长度为1; 5 } 6 for(int i = 2; i <= n; i++) 7 { 8 int len = 0; 9 for(int j = 1; j < i; j++)//a[i]前的子序列长度10 {11 if(array[j] >= array[i] && opt[j] > len)//注意此处的判断条件， 若求下降子序列则只需将>=改为<12 {13 len = opt[j];//更新最长子序列长度14 }15 }16 if(len > 0)17 opt[i] = len + 1;//a[i]时子序列长度+118 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。