TheAlgorithms/C++
1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
longest_increasing_subsequence_nlogn.cpp
1
// Program to calculate length of longest increasing subsequence in an array
2
// in O(n log n)
3
// tested on : https://cses.fi/problemset/task/1145/
4
5
#include <iostream>
6
#include <set>
7
#include <vector>
8
9
using namespace
std;
10
int
LIS(
const
std::vector<int>& arr,
int
n) {
11
set<int> active;
// The current built LIS.
12
active.insert(arr[0]);
13
// Loop through every element.
14
for
(
int
i = 1; i < n; ++i) {
15
auto
get = active.lower_bound(arr[i]);
16
if
(get == active.end()) {
17
active.insert(arr[i]);
18
}
// current element is the greatest so LIS increases by 1.
19
else
{
20
int
val = *get;
// we find the position where arr[i] will be in the
21
// LIS. If it is in the LIS already we do nothing
22
if
(val > arr[i]) {
23
// else we remove the bigger element and add a smaller element
24
// (which is arr[i]) and continue;
25
active.erase(get);
26
active.insert(arr[i]);
27
}
28
}
29
}
30
return
active.size();
// size of the LIS.
31
}
32
int
main
(
int
argc,
char
const
* argv[]) {
33
int
n;
34
cout <<
"Enter size of array: "
;
35
cin >> n;
36
std::vector<int> a(n);
37
cout <<
"Enter array elements: "
;
38
for
(
int
i = 0; i < n; ++i) {
39
cin >> a[i];
40
}
41
cout << LIS(a, n) <<
endl
;
42
return
0;
43
}
main
int main()
Main function.
Definition
generate_parentheses.cpp:110
endl
#define endl
Definition
matrix_exponentiation.cpp:36
dynamic_programming
longest_increasing_subsequence_nlogn.cpp
Generated by
1.13.2