1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <stdio.h>
#include <vector>
using namespace std;
#define INF -987654321
#define MAXLEN 10
vector<int> vt;
int main(int argc, char** argv){
int arr[MAXLEN] = {10, 20, 40, 25, 20, 50, 30, 70, 85};
vt.push_back(-INF);
for(int i=0; i<MAXLEN; i++){
if(vt.back()<arr[i])
vt.push_back(arr[i]);
else{
auto it = lower_bound(vt.begin(),vt.end(),arr[i]);
*it = arr[i];
}
}
printf("LIS : %d\n",vt.size());
return 0;
}
|
