-
Notifications
You must be signed in to change notification settings - Fork 34
/
Solution.java
37 lines (37 loc) · 853 Bytes
/
Solution.java
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
public class Solution {
int[] ans;
int length=0;
public int lengthOfLIS(int[] nums) {
ans=new int[nums.length];
for (int i = 0; i < nums.length; i++) {
f(nums[i]);
}
return length;
}
public void f(int n){
if (length==0||ans[length-1]<n) {
ans[length]=n;
length++;
}else {
int s=0;
int e=length-1;
int m=(s+e)/2;
while (e-s>1) {
if(ans[m]==n){
return;
}
if (ans[m]>n) {
e=m;
}else {
s=m;
}
m=(s+e)/2;
}
if (ans[s]>n) {
ans[s]=n;
}else {
ans[e]=n;
}
}
}
}