Description
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
1 <= nums.length <= 2500-104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
Solutions
Solution 1
| class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
f = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
f[i] = max(f[i], f[j] + 1)
return max(f)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] f = new int[n];
Arrays.fill(f, 1);
int ans = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
f[i] = Math.max(f[i], f[j] + 1);
}
}
ans = Math.max(ans, f[i]);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> f(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
return *max_element(f.begin(), f.end());
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | func lengthOfLIS(nums []int) int {
n := len(nums)
f := make([]int, n)
for i := range f {
f[i] = 1
}
ans := 1
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
f[i] = max(f[i], f[j]+1)
ans = max(ans, f[i])
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | function lengthOfLIS(nums: number[]): number {
const n = nums.length;
const f: number[] = new Array(n).fill(1);
for (let i = 1; i < n; ++i) {
for (let j = 0; j < i; ++j) {
if (nums[j
|