AlgorithmsLibrary/LongestIncreasingSubsequence(Recursive).cpp at master · PawanAIT/AlgorithmsLibrary · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
usingnamespacestd;
#defineLLlonglong
#definemp make_pair
#definepb push_back
#definemt make_tuple
#defineLDlongdouble
#definegc getchar_unlocked
#definepc putchar_unlocked
#defineMOD1000000007
#defineMAXN2*100005
#definebitcount __builtin_popcount
#defineINF2000000000
#defineEPS1e-9

template<typename T>T absll(T X)
{
if(X<0)
return -1*X;
else
return X;
}

intLIS(vector<int> A,int N,int *max_ref)
{
if(N==1)
	{
return1;
	}
int res,max_ending_here=1;

for(int i=1;i<N;i++)
	{
 res=LIS(A,i,max_ref);
if(A[N-1]>A[i-1]&&(max_ending_here)<(1+res))
 {
 max_ending_here=1+res;
 }
	}

if((*max_ref)<max_ending_here)
	{
 *max_ref=max_ending_here;
	}
return max_ending_here;
}

intmain()
{

int N,X;
scanf("%d",&N);

	vector<int> V(N,0);

for(int i=0;i<N;i++)
	{
scanf("%d",&V[i]);
	}
int maxr=1;
printf("%d\n",LIS(V,N,&maxr));
return0;
}