-
Notifications
You must be signed in to change notification settings - Fork 0
/
LIS_dp_2_binary_search.cpp
executable file
·69 lines (53 loc) · 1.46 KB
/
LIS_dp_2_binary_search.cpp
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
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
void solv(){
ll n;
cin >> n ;
vector<ll> arr(n) , dp(n+1 , INT_MAX);
for(int i = 0 ; i < n ; ++i){
cin >> arr[i];
}
// here dp[i] repesents : element at which subsequence of length i ends
// because len 0 in not available at least we have len = 1 with one element
dp[0] = INT_MIN;
// think something we can place a value at that length..
// like in earlier version if you have
// two index same length...than we'll always prefer the smaller one
// that might lead to more chances of getting that more longer increasing
// sequence...
/*
Testcase :
1
8
1 5 2 3 4 9 6 10
*/
// There is an update .... actually we are storing values in dp
// in increasing order so can we use binary search ?
// Voilla
for(int i = 0 ; i < n ; ++i){
ll j = upper_bound(dp.begin() , dp.end() , arr[i]) - dp.begin();
// cout << j << " " << endl;
if(dp[j-1] < arr[i] and dp[j] > arr[i]){
dp[j] = arr[i];
}
}
// for(int i = 0 ; i <= n ; ++i){
// cout << dp[i] << " ";
// }
// cout << "\n";
for(int i = n ; i >= 1 ; --i){
if(dp[i] != INT_MAX){
cout << i << endl;
return ;
}
}
}
int main(){
int tt = 1;
cin >> tt;
for(int i = 1; i <= tt ; ++i){
// cout << "Case #"<<i <<": ";
solv();
}
}