Thanks a lot~I got AC with this algorithm:
http://www.algorithmist.com/index.php/L ... sequence.c
However,I know this O(n^2) algorithm
and I'm now trying a O(n*log n) algorithm, can anyone help?
Moderator: Board moderators
Thanks a lot~I got AC with this algorithm:
http://www.algorithmist.com/index.php/L ... sequence.c
Code: Select all
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
using namespace std;
vector<int>a;
void LIS_seq (int len)
{
int lis [len + 10];
int index_lis [len + 10];
for ( int i = 0; i < len+10; i++ )
{
lis [i] = 1;
index_lis [i] = -1;
}
for ( int i = 1; i < len; i++ )
{
for ( int j = 0; j < i; j++ )
{
if ( a [i] > a [j]&& lis [i] < lis [j] + 1 )
{
lis [i] = lis [j] + 1;
index_lis [i] = j;
}
}
}
int max = 0;
int indexNum=0;
for ( int i = 0; i < len; i++ )
{
if ( lis [i] > max )
{
max = lis [i];
indexNum = i;
}
}
vector <int> final_list;
final_list.clear ();
while ( index_lis [indexNum] != -1 )
{
final_list.push_back (a [indexNum]);
indexNum = index_lis [indexNum];
}
final_list.push_back (a [indexNum]);
reverse (final_list.begin (), final_list.end ());
printf ("Max hits: %d\n", final_list.size ());
if(final_list.size()==1)
{
printf ("%d\n", a[len-1]);
return;
}
for ( int i = 0; i < final_list.size (); i++ )
printf ("%d\n", final_list [i]);
}
int main ()
{
int length = 0;
int kase;
cin>>kase;
getchar();
getchar();
puts("");
int cas;
for(cas=1; cas<=kase; cas++)
{
if(cas>1)
printf("\n");
length=0;
char array[19];
while ( gets(array) )
{
int len=strlen(array);
if(array==NULL)break;
if(len==0||array[0]=='\0')break;
a.push_back(atoi(array));
length++;
}
if(length==0)
{
printf ("Max hits: %d\n", length);
continue;
}
LIS_seq(a.size());
a.clear();
}
return 0;
}
Code: Select all
#include<iostream>
#include<fstream>
#include<sstream>
#include<cstdio>
#include<stdlib.h>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef string str;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef vector<ll> vin;
typedef vector<string> vs;
typedef vector<vector<ll> > vvin;
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define BREP(i,a,b) for(ll i=a-1;i>=b;i--)
#define brep(i,n) BREP(i,n,0)
#define pb push_back
#define inf 999999999
#define SIZE 10000
#define mp make_pair
#define sz size()
#define NIL 0
#define DEBUG 0
#define all(vec) (vec).begin(),(vec).end()
#define NEG -1
vin heights(SIZE,NIL),ret(SIZE,NIL),predecessors(SIZE,NEG);
int last_boss;
void init() {
rep(i,SIZE) {
ret[i]=1;
predecessors[i]=NEG;
}
last_boss=NEG;
}
void solve(int syze) {
int max_len=NIL;
vin temp;
rep(i,syze)
rep(j,i) {
if(ret[j]+1>ret[i] && heights[j]<heights[i]) {
ret[i]=ret[j]+1;
predecessors[i]=j;
if(max_len<ret[i]) {
last_boss=i;
max_len=ret[i];
}
}
}
cout<<max_len;
while(last_boss!=-1) {
temp.pb(heights[last_boss]);
last_boss=predecessors[last_boss];
}
brep(i,temp.sz)
cout<<"\n"<<temp[i];
}
int main() {
int test_cases,height,index;
stringstream ss;
str str1;
getline(cin,str1);
ss<<str1;
ss>>test_cases;
getline(cin,str1); //for blank line
rep(i,test_cases) {
init();
index=0;
if(i!=0)
cout<<"\n\n";
while(getline(cin,str1)) {
if(str1=="")
break;
stringstream converter;
converter<<str1;
converter>>height;
heights[index++]=height;
}
cout<<"Max hits: ";
solve(index);
}
return 0;
}
Code: Select all
#include <iostream>
#include<cmath>
#include<cstdio>
#include<vector>
using namespace std;
int lis_seqence[300000];
int L[300000];
int LIS(int n)
{
for(int i=0;i<=n;i++)
L[i]=1;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(lis_seqence[i]<lis_seqence[j])
{
if(L[j]<L[i]+1)
L[j]=L[i]+1;
}
}
}
int maxLength=0;
for(int i=0;i<n;i++)
if(maxLength<L[i])
maxLength=L[i];
cout<<"Max hits: "<<maxLength<<endl;
return maxLength;
}
void LIS_find_sequence(int maxLength,int n)
{
vector<int>v;
int i;
for(i=0;i<n;i++)
if(maxLength==L[i])
break;
v.push_back(lis_seqence[i]);
for(int j=i-1;j>=0;j--)
{
if((L[i]-L[j])==1 && lis_seqence[j]<lis_seqence[i])
{
int a = j;
int b =j;
int c = i;
while(a!=-1)
{
if((L[i]-L[a])==1 && lis_seqence[a]<lis_seqence[i])
{
c=a;
b=a;
}
a--;
}
i=c;
j=b;
v.push_back(lis_seqence[j]);
i=j;
}
}
for(i=v.size()-1;i>=0;i--)
cout<<v[i]<<endl;
v.clear();
}
int main()
{
int b;
cin>>b;
getchar();
getchar();
string s;
for(int j=1;j<=b;j++)
{
int k =0;
while(1)
{
int a = 0;
getline(cin,s);
if(s=="")
break;
for(int i=0;i<s.size();i++)
a = a +(s[i]-48);
lis_seqence[k++] = a;
}
int maximum=LIS(k);
LIS_find_sequence(maximum,k);
if(j!=b)
cout<<endl;
}
return 0;
}
Code: Select all
2
1
6
2
3
5
1
6
2
3
5
Code: Select all
Max hits: 4
1
2
3
5
Max hits: 4
1
2
3
5
Code: Select all
Removed after getting accepted
Thanks for replying brianfry713, please see the updated code with includes in my original post.brianfry713 wrote:That code won't compile without the includes.
http://en.wikipedia.org/wiki/Longest_in ... ubsequence