首页 > 代码库 > 动规(LIS)-POJ-2533
动规(LIS)-POJ-2533
http://poj.org/problem?id=2533
Longest Ordered Subsequence
给定n个正整数,求最长上升子序列(LIS)长度(子序列中的元素不要求连续).
解题报告
思路
经典的LIS问题,O(n^2)的朴素做法不多作介绍,仅仅介绍O(n logn)的做法。
对于n个元素的数组array,建立一个数组d[n]。
其中d[i]表示长度为i的子序列中最小的末尾元素为d[i]。
数组d显然是升序的,可用反证法证明:
假设存在d[i]>=d[j]且i<j。
那么由于i<j,那么在d[j]结尾的子序列中,必然存在某个值array[k]<d[j]<=d[i],使得以array[k]结尾的LIS长度为i,因而与假设矛盾。
根据d数组的升序性质,可以循环遍历array数组:
对于遍历到的array[i],在d数组中二分查找最后一个小于array[i]的元素d[k],那么以array[i]结尾的LIS的长度则为k+1。同时更新d数组。
那么时间复杂度就为O(n logn)
代码
#include <algorithm> #include <cstring> #include <iostream> using namespace std; const int maxn = 1003; const int INF = 0x3f3f3f3f; int minNum[maxn]; int n; int main() { ios::sync_with_stdio(false); cin.tie(0); while (cin >> n) { memset(minNum, INF, sizeof(minNum)); minNum[0] = -1; int num, len, ans = 1; for (int i = 0; i < n; i++) { cin >> num; len = lower_bound(minNum, minNum + n, num) - minNum; if(minNum[len] == num) len--; minNum[len] = min(minNum[len], num); ans = max(ans, len); } cout << ans << endl; } return 0; }
动规(LIS)-POJ-2533
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。