首页 > 代码库 > 【编程题目】求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5， 4，3，2}
【编程题目】求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5， 4，3，2}
47.创新工场（算法）：
求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，
4，3，2}
思路：动态规划
从最后一个数字开始，计算以当前数字其实的序列的最长递减子序列。 每次找最长子序列，都扫描它之前求得的子序列中最长，且第一个数字比当前数字小的。
如： 第一个数字 2， 最大长度 1， 下一个数字是 第 7 个
第二个数字 3， 最大长度 2， 下一个数字是 第 7 个
第三个数字 4， 最大长度 3， 下一个数字是 第 6 个
第四个数字 5， 最大长度 4， 下一个数字是 第 5 个
第五个数字 2， 最大长度 1， 下一个数字是 第 3 个
第六个数字 3， 最大长度 2， 下一个数字是 第 3 个
第七个数字 4， 最大长度 3， 下一个数字是 第 2 个
第八个数字 9， 最大长度 5， 下一个数字是 第 4 个
这样就可以找到最大长度，并根据存储的下一个数字找到最长递减序列。
/*47.创新工场（算法）：求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}*/#include <stdio.h>#include <stdlib.h>int maxLength(int * a, int len){ int * pos = (int *)malloc(2 * len * sizeof(int)); //找到以每一个元素起始的最长递减子序列 pos[2 * (len - 1)] = 1; //以最后一个数字为首的最长递减子序列长度 pos[2 * len - 1] = len - 1; //最后一个数的下一个数字 for (int i = len - 2; i >= 0; i--) { int maxlen = 0; int nextpos = i; for (int j = i + 1; j < len; j++) { if (a[j] < a[i]) { if (pos[2 * j] > maxlen) { maxlen = pos[2 *j]; nextpos = j; } } } pos[2 * i] = maxlen + 1; //以a[i]为首的最长递减子序列长度 pos[2 * i + 1] = nextpos; //a[i]的下一个数字 } //找到最长的递减序列 int maxstart = 0; int max = 0; for (int i = 0; i < len; i++) { if (pos[2 * i] > max) { max = pos[2 * i]; maxstart = i; } } //打印最长递减子序列 printf("最长递减子序列为："); int next = maxstart; do { printf("%d ", a[next]); next = pos[2 * next + 1]; }while(next != pos[2 * next + 1]); printf("%d\n", a[next]); free(pos); return max; //返回最大长度}int main(){ int a[8] = {9,4,3,2,5,4,3,2}; int len = maxLength(a,8); return 0;}
发现我又有一个地方傻×了，其实可以不用存下一个数字的位置的，直接查找最大长度少一的数字并打印就可以了。
如下：http://blog.csdn.net/wumuzi520/article/details/7378306
#include <iostream>#include <cstring>using namespace std;int Fun(int aIn[],int pTable[],int nLen){ int nMaxLen = 0; for(int i = nLen-1; i >= 0; --i) { int nMax = 0; for(int j = i+1; j < nLen; ++j) { if(aIn[j] < aIn[i]) { nMax = nMax < pTable[j] ? pTable[j] : nMax; } } pTable[i] = 1+nMax; nMaxLen = nMaxLen<pTable[i] ? pTable[i] : nMaxLen; } return nMaxLen;}void PrintMaxSubsequence(int aIn[], int pTable[], int nMaxLen, int nLen) //!!!!!!!!!!{ for(int i = 0,j=0; i < nLen; ++i) { if(pTable[i] == nMaxLen){ cout << aIn[i] << " "; nMaxLen--; } } cout << endl;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。