首页 > 代码库 > [算法]求数组中最长递增子序列长度
[算法]求数组中最长递增子序列长度
思路：
1、开辟数组L,L[i]记录的为a[0]~a[i]的最长递增子序列长度
2、开辟数组maxV，maxV[i]记录的为长度为i的各递增子序列的最后一个元素的最小值，譬如有子序列
1,2,4
1,2,5
则maxV[3] = 4
3、使用maxLen记录当前的最长递增子序列长度
4、转移方程： L[i+1] = max{1,L[j]+1] , a[i] > maxV[j] && j <= maxLen
int LIS(int* a, int n){ int* maxV = new int[n+1]; int* L = new int[n]; maxV[1] = a[0]; L[0] = 1; int maxLen = 1; for(int i = 1, j; i < n; ++i){ L[i] = 1; for(j = maxLen; j >= 1; --j){ if(maxV[j] < a[i]){ L[i] = j+1; break; } } if(L[i] > maxLen){ maxLen = L[i]; maxV[maxLen] = a[i]; } else{ if(j >= 1 && maxV[j+1] > a[i]){ maxV[j+1] = a[i]; } } } delete[] maxV; delete[] L; return maxLen;}
参考编程艺术2.16
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。