网页制作与网站开发从入门到精通 豆瓣,wordpress插件更新保留修改,网站建设怎么做,聊城城乡建设局网站1.问题描述#xff1a;求一个正整数序列的最长单调自增子序列#xff0c;子序列不要求是连续的。例如Input#xff1a;55 2 4 3 1Output#xff1a;22. 算法复杂度是O(N*N)f[i]是以a[i]为最大值的子序列#xff0c;那么f[]的最大值就是要的结果。int f[],a[];f[0] 1;for(… 1.问题描述求一个正整数序列的最长单调自增子序列子序列不要求是连续的。例如Input55 2 4 3 1Output22. 算法复杂度是O(N*N)f[i]是以a[i]为最大值的子序列那么f[]的最大值就是要的结果。int f[],a[];f[0] 1;for(i 1 ; i n ; i ){ f[i] 1; for(j 0 ; j i ; j) { If(a[j] a[i] f[j]1 f[i])//等号有没有要视题目而定 { f[i] f[j] 1; } }}很显然实践复杂度是O(N*N)那么有没有更快的算法呢按照正常的思路更快的复杂度应该就是O(N*logN)那么就要涉及到二分了。 3. 算法复杂度是O(N*logN)可是话又说回来那个logN到底怎么实现的呢上网搜了搜说的都有点抽象捉摸了一下是这个样子滴建立一个辅助数组c[n]c[i]存储的是子序列长度为i的序列最后一个值实际上子序列长度为i的子序列有多个要的是子序列最后一个值最小的。后面解释后什么。这时要遍历要处理的数组a[n]for(i1;in;i)//从第二值开始因为第一个值用来初始化了{ jfind(c,n1,a[i]);//find是一个二分查找 c[j]a[i]; b[i]j;}请看一下上面的例子实际执行的情况C数组变化的情况-1 5-1 2-1 2 4-1 1 2-1 1 4-1 1 3A数组遍历是从前往后的处理a[i-1]时a[i]以及后面的值肯定还没有处理前面的值都处理过了看c数组每个a数组中的值和c数组中值进行比较找到合适的位置插入若插入到c数组的末尾那么就属于最长递增子序列长度加1实际上c数组的长度就是最后的最长单调递增子序列的长度。否则这就替换掉了c数组中原来位置存储的值这种替换时有意义的主要是为了后来的a数组中的值计算b用b[i]中保存的是以a[i]为最后一个元素的最长单调递增子序列。好处是若a[i] a[j],b[i]b[j]那么在c中肯定要保存a[i]呀注意c数组的下标代表的是子序列的长度c数组中的值也是按递增顺序排列的。这才可能用二分呢亲。和O(N*N)的主要区别就是巧妙的借用了c数组本题的关键就是理解c数组的意义。可以手动模拟一下算法执行的步骤重要模拟c和b数组的变化情况。下面给出完整的算法。 #include iostreamusing namespace std; int find(int *a,int len,int n)//二分find{ int left0,rightlen,mid(leftright)/2; while(leftright) { if(na[mid]) leftmid1; else if(na[mid]) rightmid-1; else return mid; mid(leftright)/2; } return left;}void fill(int *a,int n){ for(int i0;in;i) a[i]1000;//这就是一个初始化无所谓!!}int main(){ int max,i,j,n,a[100],b[100],c[100]; while(cinn) { fill(c,n1); for(i0;in;i) cina[i]; c[0]-1;//要懂得用这种天然的最小值 c[1]a[0];//初始化 b[0]1;//b[i]表示以a[i]结尾的最长单调递增子序列 for(i1;in;i)//复杂度是N的 { jfind(c,n1,a[i]);//复杂度是logN的 c[j]a[i]; b[i]j; } for(maxi0;in;i)//遍历一遍找到最大值 if(b[i]max) maxb[i]; coutmaxendl; } return 0;} 转载于:https://blog.51cto.com/liuyuanxing/1926375
