CODEVS 1576 最长严格上升子序列数据结构与算法

题目链接 1576 最长严格上升子序列
题意

找出一个序列中上升子序列
例如 2 1 5 3 6 4 8 9 7
上升子序列：1 5 6 8 9 或者 1 3 4 8 9 但是子序列长度都是5

思路

【CODEVS 1576 最长严格上升子序列】有两种想法：一是动归，一是每次从前往后找第一大并且替换。这样做的能得到最长序列的次数，但是无法知道最长序列是什么。

代码动归

#includeusing std::cin; using std::cout; using std::endl; int size; //数组长度 int a[5001]; //原数组 int dp[5001]; //序列长度数组int main(int argc,char *argv[]) { cin >> size; for(int i = 0; i < size; i++) { cin >> a[i]; dp[i] = 1; } for(int i = 0; i < size; i++) { for(int j = 0; j < i+1; j++) { if((a[i] > a[j]) && dp[j]+1 > dp[i]) { dp[i] = dp[j]+1; //动归的递推式 } } } int max = 1; for(int i = 0; i < size; i++) {//找出最大值 if(dp[i] > max) { max = dp[i]; } } cout << max << endl; return 0; }

O(n^2)

#includeusing std::cin; using std::cout; using std::endl; int size; //a数组大小 int a[5001]; //原数组 int dp[5001]; //和子序列个数相同的数组，但是元素不一定是子序列 int len = 0; //dp数组长度 int flag = 0; int main(int argc,char *argv[]) { cin >> size; for(int i = 0; i < size; i++) { cin >> a[i]; } dp[0] = a[0]; len++; for(int i = 0; i < size; i++) { flag = 0; for(int j = 0; j < len; j++) { if(a[i] <= dp[j]) { dp[j] = a[i]; flag = 1; break; } } if(flag == 0) { dp[len] = a[i]; len++; } } cout << len << endl; return 0; }

二分优化方法二，为O(nlog(n))

#includeusing std::cin; using std::cout; using std::endl; int size; //a数组长度 int a[100]; int dp[100]; int len = 0; int max = 0; //dp数组长度,也就是最大字串的长度。void findFirstBig(int begin,int end,int find)//二分查找dp数组中第一个比find大的元素 { while(begin <= end) { int mid = (begin+end)/2; if(dp[mid] == find) { return; } if(dp[mid] < find) begin = mid+1; if(dp[mid] > find) end = mid-1; } len = begin; }int main(int argc,char *argv[]) { cin >> size; for(int i = 0; i < size; i++) { cin >> a[i]; } dp[0] = a[0]; for(int i = 0; i < size; i++) { if(a[i] > dp[max]) {//如果下一个元素比dp数组中最大的还大 max++; dp[max] = a[i]; } else { findFirstBig(0,max,a[i]); dp[len] = a[i]; } } cout << max+1 << endl; return 0; }