http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
#include <map>
9
using
namespace
std;
10
11
int
maxsum(
int
arr[],
int
n) {
12
vector<
int
>
tail;
13
tail.push_back(arr[
0
]);
14
for
(
int
i =
1
; i < n; i++
) {
15
if
(arr[i] < tail[
0
]) tail[
0
] = arr[
0
];
16
else
if
(arr[i] > tail[tail.size()-
1
]) tail.push_back(arr[i]);
17
else
{
18
int
mid;
19
int
left =
0
;
20
int
right = tail.size() -
1
;
21
while
(left <
right) {
22
mid = (left + right) /
2
;
23
if
(tail[mid] < arr[i]) left = mid +
1
;
24
else
right = mid -
1
;
25
}
26
mid = (left + right) /
2
;
27
tail[mid] =
arr[i];
28
cout <<
"
tail[
"
<< mid <<
"
] is arr[
"
<< i <<
"
] =
"
<< arr[i] <<
endl;
29
}
30
}
31
return
tail.size();
32
}
33
34
int
main() {
35
int
arr[
9
] = {
2
,
5
,
3
,
7
,
11
,
8
,
10
,
13
,
6
};
36
cout << maxsum(arr,
9
) <<
endl;
37
return
0
;
38
}
Data Structure Array: Longest Monotonically Increasing Subsequence Size
