Longest Increasing Subsequence
Leetcode https://leetcode.cn/problems/longest-increasing-subsequence
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
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] longest = new int[nums.length];
longest[0] = 1;
int maxLength = 1;
for (int i = 1; i < nums.length; i++) {
longest[i] = 1;
for (int j = i - 1; j >= 0; j--) {
if (nums[i] > nums[j]) {
longest[i] = Math.max(longest[i], longest[j] + 1);
}
}
maxLength = Math.max(maxLength, longest[i]);
}
return maxLength;
}
}
Complexity
- Time = O(n^2)
- Space = O(n)
This post is licensed under CC BY 4.0 by the author.