I wrote a solution to this question. The task is to take an input of n increasing positive integers (1 ≤ n ≤ 2∙105), each entry as large as 109, and find the length of the longest subsequence where each element is no more than double the previous element.
Example input
10
1 2 5 6 7 10 21 23 24 49
Example output
4
… because the longest subsequence is [5, 6, 7, 10].
My solution works for small numbers, but exceeds the time limit for big inputs.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n,a,c=1,max_count=1;
cin>>n;
vector<int>v;
for(int i=0;i<n;i++)
{
cin>>a;
v.push_back(a);
}
for(int i=0;i<n;i++)
{
int l=i+1;
while((l<n)&&(v[l]<=2*v[i]))
{
c++;
l++;
max_count=max(max_count,c);
}
c=1;
}
cout<<""<<max_count;
return 0;
}