-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLengthOfLIS.java
More file actions
37 lines (31 loc) · 771 Bytes
/
Copy pathLengthOfLIS.java
File metadata and controls
37 lines (31 loc) · 771 Bytes
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
import java.util.Arrays;
/**
* 300. 最长递增子序列
*/
public class LengthOfLIS {
public int lengthOfLIS(int[] nums) {
int[] memo=new int[nums.length];
Arrays.fill(memo, -1);
memo[0]=1;
dp(nums.length-1, nums, memo);
int res=1;
for(int t: memo){
res = Math.max(res, t);
}
return res;
}
int dp(int start, int[] nums, int[] memo){
if(memo[start]!=-1){
return memo[start];
}
int res=1;
for(int i=start-1; i>=0; i--){
int temp = dp(i, nums, memo);
if(nums[i]<nums[start]){
res = Math.max(res, temp+1);
}
}
memo[start] = res;
return memo[start];
}
}