首页 > 代码库 > 最长单调递减子序列
最长单调递减子序列
问题描述:求一个数组的最长递减子序列 比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}。
思路:这是一个标准的动态规划的问题,在不理解算法的时候,最感觉可以使用递归的思想,其实也是正确的,在最后给出一个递归的方法,在知道是动态规划问题以后,就需要进行分析,我们需要一个辅助数组记录信息,假如源数组为src,辅助数组为table,table[i]数组中记录着到src[0]~src[i]这个子数组中包含src[i]构成的最长单调子序列的长度(一定要注意就是table[i]记录了包含src[i]构成的递减序列中最长的那个,也就是以src[i]为结尾的最长递减子序列),如果src[i]大于以前的所有元素,那么table[i]=1.
最后的结果就是,table[i] =max{table[k]+1, src[i] > src[k] && 0<k<i},这是初始化了table数组,那么最长递减子序列为max{table[i],0<i<n}.
但是需要打印最长子序列,我们已经记录了max{table[i],0<i<n}的下标,那么我们就知道了最长子序列的最后一个元素,同时知道了最长子序列的长度。下面就是递归调用,假如我们已经知道table[k]最大,那么src[k]就是最长递减子序列中的最后一个,如果table[i]+1 = table[k] && src[i] < table[k]时,那么就需要答应src[i]。
#include <stdio.h> #include <stdlib.h> void Find(int src[],int n,int table[]) { table[0]= 1; int i,j,maxi = 0; for(i=0;i<n;i++) { table[i]=1; for(j=0;j<i;j++) { /* 这里可能是常有的错误 if( src[j] > src[i]) { table[i] = table[j] +1; if(src[j]>src[i]) table[i] = table[j]+1; if(table[i] > table[maxi]) maxi = i; } */ if(src[j]> src[i] && table[j]+1 > table[i]) { table[i] = table[j]+1; //这个的作用是为了打印存在的,maxi记录最长子序列中最后一个数组元素 if(table[i] > table[maxi]) maxi = i; } } } // printf("%d\r\n",maxi); } void print(int src[],int table[],int maxi) { int i=maxi-1; for(;i>=0;i--) { if(table[maxi] == table[i]+1 && src[i] > src[maxi]) { print(src,table,i); break; } } printf("%d ",src[maxi]); } void FindLongestDSCArray2(int *arr, int n){ int mark[9]; int link[9]; int i = 0; for(i=0;i<n;i++){ mark[i] = 0; link[i] = -1; } //link[0] = 1; int j = 0, maxMark = 0; for(i=0;i<n;i++){ maxMark = 0; for(j=0;j<i;j++){ if(arr[j]>arr[i]){ if(maxMark<mark[j]){ maxMark = mark[j]; link[i] = j; } } } mark[i] = maxMark+1; } for(i=0;i<9;i++) printf("%d ",mark[i]); printf("\r\n"); for(i=0;i<9;i++) printf("%d ",link[i]); printf("\r\n"); /* //Print() int node = 0; maxMark = 0; for(i=0;i<n;i++){ if(mark[i]>maxMark) node = i; } while(node != -1){ printf("%d ",arr[node]); node = link[node]; } */ } int main() { int src[]={9,4,3,2,5,4,3,2,4}; int table[9]; Find(src,9,table); FindLongestDSCArray2(src,9); int i=0; for(;i<9;i++) printf("%d ",table[i]); printf("\r\n"); return 0; }
最长单调递减子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。