首页 > 代码库 > NYOJ214
NYOJ214
单调递增子序列(二)
时间限制:1000 ms | 内存限制:65535 KB
难度:4
- 描述
给定一整型数列{a1,a2...,an}(0<n<=100000),找出单调递增最长子序列,并求出其长度。
如:1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13,长度为5。
- 输入
- 有多组测试数据(<=7)
每组测试数据的第一行是一个整数n表示序列中共有n个整数,随后的下一行里有n个整数,表示数列中的所有元素.每个整形数中间用空格间隔开(0<n<=100000)。
数据以EOF结束 。
输入数据保证合法(全为int型整数)! - 输出
- 对于每组测试数据输出整形数列的最长递增子序列的长度,每个输出占一行。
- 这个与单调递增子序列(一)有些不同,
- (一)
- 在单调递增子序列一中,可以用一个数组保存当前位置之前的最大子序列长度,可以在一次遍历数组串,每次查询之前的数组小于当前数的最大值,这样的
- 时间复杂度就是0 + 1 + 2 + ... + n-1 = (n-1)*n/2 即O(n2)
- 例如输入:【2,3,1,2,3】
- 结果数组:【1,0,0,0,0】
- 【1,2,0,0,0】
- 【1,2,1,0,0】
- 【1,2,1,2,0】
- 【1,2,1,2,3】
- 结果是3
- (二)的话可以用一个数组记录当前最大字符串长度,判断当前数与数组顶部的值大小,(1)如果大于数组顶的数则直接添加到尾部,数组长度加1
- (2)在数组中找到一个数,这个数是大于等于当前数的最小的
- (可以用二分法时间复杂度O(nlogn))
- 比如输入【2,3,1,2,3】
- 数组变化:
- 【2】
- 【2,3】
- 【1,3】
- 【1,2】
- 【1,2,3】
- 不过这个方法只能求出最大递增子序列长度
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 int riseSubString(int a[], int n) 5 { 6 int i,l,r,m,s[100000],top = 0; 7 if (n == 0) 8 return 0; 9 s[0] = a[0];10 for (i=1; i < n; i++)11 {12 if (s[top] < a[i])13 s[++top] = a[i];14 else15 {16 l = 0;17 r = top;18 m = top / 2;19 while ((l + 1) < r) //二分,l与r间隔1时结束循环,再判断哪个是大于a[i]最小值20 {21 if (a[i] <= s[m])22 {23 r = m;24 m = (r+l)/2;25 }26 else27 {28 l = m;29 m = (l+r)/2;30 }31 }32 if (s[l] > a[i])33 s[l] = a[i];34 else35 s[r] = a[i];36 }37 }38 return top + 1;39 }40 int main()41 {42 int a[100001];43 int n,i;44 while (scanf("%d",&n) != -1){45 for (i=0; i < n; i++)46 scanf("%d",&a[i]);47 printf("%d\n",riseSubString(a,n));48 }49 return 0;50 }
NYOJ214
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。