FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java-Competitive-Programming/Algorithms/LIS_nLOGn.java at master · joney000/Java-Competitive-Programming · GitHub
joney000
/
Java-Competitive-Programming
Public
Notifications
You must be signed in to change notification settings
Fork
30
Star
123
Code
Issues
0
Pull requests
1
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java-Competitive-Programming
/
Algorithms
/
LIS_nLOGn.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
executable file
·
128 lines (82 loc) · 2.47 KB
Breadcrumbs
Java-Competitive-Programming
/
Algorithms
/
LIS_nLOGn.java
Copy path
File metadata and controls
executable file
·
128 lines (82 loc) · 2.47 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/* package joney_000 */
import
java
.
util
.*;
import
java
.
lang
.*;
import
java
.
io
.*;
import
java
.
math
.*;
// return LIS;
class
LIS_nLOGn
{
public
static
long
ans
=
0
;
BufferedReader
br
=
new
BufferedReader
(
new
InputStreamReader
(
System
.
in
));
BufferedWriter
out
=
new
BufferedWriter
(
new
OutputStreamWriter
(
System
.
out
));
public
static
void
main
(
String
[]
args
)
throws
Exception
{
ans
=
0
;
int
tests
=
Integer
.
parseInt
(
br
.
readLine
());
for
(
int
t
=
0
;
t
<
tests
;
t
++){
int
n
=
Integer
.
parseInt
(
br
.
readLine
());
int
num
[]=
new
int
[
n
];
String
[]
s
=
br
.
readLine
().
split
(
" "
);
for
(
int
i
=
0
;
i
<
n
;
i
++){
num
[
i
]=
Integer
.
parseInt
(
s
[
i
]);
}
long
ans
=
findLIS
(
num
);
ans
= (
ans
*(
ans
-
1
)*(
ans
-
2
))/
6
;
out
.
write
(
""
+
ans
+
"
\n
"
);
out
.
flush
();
}
}
public
static
int
search
(
int
[]
M
,
int
[]
A
,
int
i
,
int
L
) {
int
j
=
0
;
int
k
=
L
-
1
;
while
(
j
<=
k
) {
int
m
= (
j
+
k
) /
2
;
if
(
A
[
M
[
m
]] <=
A
[
i
] )
j
=
m
+
1
;
else
k
=
m
-
1
;
}
return
k
;
}
public
static
int
findLIS
(
int
[]
A
) {
int
n
=
A
.
length
;
int
[]
M
=
new
int
[
n
];
int
[]
P
=
new
int
[
n
];
M
[
0
] =
0
;
P
[
0
] = -
1
;
int
L
=
1
;
for
(
int
i
=
1
;
i
<
n
; ++
i
) {
int
j
=
search
(
M
,
A
,
i
,
L
);
if
(
j
== -
1
)
P
[
i
] = -
1
;
else
P
[
i
] =
M
[
j
];
if
(
j
==
L
-
1
||
A
[
i
] <
A
[
M
[
j
+
1
]] ) {
M
[
j
+
1
] =
i
;
if
(
j
+
2
>
L
)
L
=
j
+
2
;
}
}
int
[]
LIS
=
new
int
[
L
];
n
=
L
-
1
;
int
p
=
M
[
n
];
while
(
n
>=
0
) {
LIS
[
n
] =
A
[
p
];
p
=
P
[
p
];
n
--;
}
return
L
;
}
//example A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
public
static
void
PrintLis
(
int
[]
n
)
throws
Exception
{
int
[]
li
=
new
int
[
n
.
length
()];
// holds the lis numbers index (indirectly numbers of maximum lis sequence)
int
[]
pi
=
new
int
[
n
.
length
()];
// holds previous index of current maximum lis no
int
size
=
0
;
//size of maximum lis
li
[
0
]=
0
;
pi
[
0
]=-
1
;
size
=
1
;
for
(
int
i
=
1
;
i
<
n
.
length
();
i
++){
if
(
n
[
i
]<
n
[
li
[
0
]]){
li
[
0
]=
i
;
}
else
if
(
n
[
i
]>
li
[
size
-
1
]){
pi
[
i
]=
li
[
size
-
1
];
li
[
size
]=
i
;
size
++;
}
else
if
()
}
}
}
Back
|
FazBrowse Home
|
New Git URL