单调递增子序列(二)
时间限制:1000 ms | 内存限制:65535 KB
难度:4
给定一整型数列{a1,a2...,an}(0<n<=100000),找出单调递增最长子序列,并求出其长度。
如:1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13,长度为5。
每组测试数据的第一行是一个整数n表示序列中共有n个整数,随后的下一行里有n个整数,表示数列中的所有元素.每个整形数中间用空格间隔开(0<n<=100000)。
数据以EOF结束 。
输入数据保证合法(全为int型整数)!
7 1 9 10 5 11 2 13 2 2 -1
5 1
思路:
最长上升子序列。
同样需要用 n log n 的写法来优化,除此之外,不能初始化第一个数为 -1,因为序列中的数有可能出现负数,所以直接将第一个数放进去考虑,最后长度输出 len + 1 即可(因为下标是从 0 开始的)。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int num[100005]; int main() { int n; while (~scanf("%d", &n)) { int len = 0; scanf("%d", &num[len]); --n; while (n--) { int ans; scanf("%d", &ans); if (ans > num[len]) num[++len] = ans; else *lower_bound(num, num + len, ans) = ans; } printf("%d\n", len + 1); } return 0; }
相关推荐
此程序用C程序设计语言编写,用于找出序列当中最长递增子序列。
动态规划的经典题目最长上升子序列,而且是经过二分优化的NlogN复杂度算法
此资源有助于帮助初学者较快掌握nlogn算法求动态规划中的经典例题---最长不上升序列(n>100000)
##算法最长递增子序列时间复杂度O(nlogn)##接口JAVA swing ##功能更改输入字符串的长度随机生成输入字符串标记输入字符串中最长的递增子序列
最长递增子序列 O(Nlogn) 最长的子阵列 矩阵链顺序 最大非邻和 最大乘积子阵列 最大子数组 最大和连续子序列 底部的最小距离 最小硬币兑换 最低成本路径 最小分区 最小大小子阵列总和 表示数字的最小...
关于用nlogn的最长子序列算法,在网上摘录的
最近邻点对O(n^2)和O(nlogn)算法
求一组数的最长上升子序列,时间复杂度为O(nlogn)
逆序对(归并排序)O(nlogn).cpp
北大POJ1836-Alignment【O(nlogn)】
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
北大POJ1804-Brainman【借助Mergesort求逆序数O(nlogn)】
算法之NlogN排序算法(csdn)————程序
LIS 最长上升子序列O(NLOGN) 3 RMQ 区间最值询问3 KMP 模式匹配3 字符串最小表示4 第二章数据结构5 并查集5 HEAP 最小堆5 树状数组6 二维树状数组6 TRIE 字典树6 后缀数组8 LCP 最长公共前缀9 第三章图论11 ...
5.3 最长上升子序列/最长不下降子序列(LIS) 65 5.3.1 O(n^2) 65 5.3.2 O(nlogn) 66 5.4 Joseph问题 67 5.5 0/1背包问题 68 6 组合数学相关 69 6.1 The Number of the Same BST 69 6.2 排列生成 71 6.3 逆序 72 6.3.1...
快速排序描述:快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序...
5.3 最长上升子序列/最长不下降子序列(LIS) 65 5.3.1 O(n^2) 65 5.3.2 O(nlogn) 66 5.4 Joseph问题 67 5.5 0/1背包问题 68 6 组合数学相关 69 6.1 The Number of the Same BST 69 6.2 排列生成 71 6.3 逆序 72 6.3.1...
python 归并排序算法 归并排序是一种基于分治思想的排序算法,它将待排序的序列分成若干个子序列,每个子序列都是有序的,然后再将这些有序的子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn),是一种...
要求算法的时间复杂度不超过O(nlogn)。 最大子段和问题描述:给定由n个整数(可能为负整数)组成的序列a1, a2,…, an, 求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义,所求...