Responsive image

问题 2605 --最长子序列

2605: 最长子序列

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 7
[提交][状态][讨论版][命题人:]

题目描述

给定一个长度为 n 的严格单调递增的整数序列 a1,a2,…,an。

序列 a 的子序列可以表示为 ai1,ai2,…,aip，其中 1≤i1<i2<…<ip≤n。

我们希望找到一个 a 的子序列，使得该子序列满足：对于 j∈[1,p−1]，aij+1≤aij×2 恒成立。

我们认为，长度为 1 的子序列总是满足条件的。

请你计算并输出满足条件的子序列的最大可能长度。

输入描述

第一行包含一个整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出描述

一个整数，表示满足条件的子序列的最大可能长度。

样例输入

10
1 2 5 6 7 10 21 23 24 49

样例输出

4

提示

前 5 个测试点满足 1≤n≤10。

所有测试点满足 1≤n≤2×105，1≤a1<a2<…<an≤109。

来源

21软四焦霄佳 

[提交][状态]
ACM算法攻关部