首页 > 代码库 > nlog(n)解动态规划--最长上升子序列(Longest increasing subsequence)
nlog(n)解动态规划--最长上升子序列(Longest increasing subsequence)
最长上升子序列LIS问题属于动态规划的初级问题，用纯动态规划的方法来求解的时间复杂度是O(n^2)。但是如果加上二叉搜索的方法，那么时间复杂度可以降到nlog(n)。
具体分析参考：http://blog.chinaunix.net/uid-26548237-id-3757779.html
代码：
#include <iostream>using namespace std;int LIS_nlogn(int *arr, int len){ int *LIS = new int[len]; //LIS[i]存储的是每个最长长度i的最小结尾,即在arr里的最小结尾 for (int i = 0; i < len; i++) { LIS[i] = -1; } int maxLen = 1; //记录最长上升子串的最大长度 LIS[0] = arr[0]; for (int i = 0; i < len; ++i) { int low = 0, high = maxLen, mid; while (low <= high) { mid = (low + high)/2; if (LIS[mid] < arr[i]) { low = mid + 1; } else { high = mid - 1; } } LIS[low] = arr[i]; //插入元素到相应的位置 if (low > maxLen) { maxLen++; } } delete LIS; return maxLen;}int main(){ int arr[] = {2,1,5,3,6,4,8,9,7}; int len = 9; int ret; ret = LIS_nlogn(arr, len); cout<<ret<<endl; return 0;}
nlog(n)解动态规划--最长上升子序列(Longest increasing subsequence)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。