• ㊗️
• 大家
• offer
• 多多！

Problem

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
• $-10^4 <= nums[i] <= 10^4$

Code

[10,9,2,5,3,7,101,18]

[2147483647,2,3,7,18,2147483647,2147483647,2147483647,2147483647]

class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length + 1];
Arrays.fill(tails, Integer.MAX_VALUE);

for(int num : nums){
int index = helper(tails, num);
tails[index] = num;
}

int res = 0;

for(int num : tails){
if(num != Integer.MAX_VALUE){
res++;
}
}

return res;
}

private int helper(int[] nums, int target){
int start = 0;
int end = nums.length - 1;

while(start + 1 < end){
int mid = (start + end) / 2;

if(nums[mid] == target) return mid;

if(nums[mid] < target){
start = mid;
} else {
end = mid;
}
}

return end;
}
}

class Solution {
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);

int res = 1;

for(int i = 1; i < nums.length; i++){
for (int j = 0; j < i; j++){
if (nums[i] > nums[j]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}

res = Math.max(res, dp[i]);
}

return res;
}
}

class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
dp = [1] * len(nums)

res = 1

for i in range(1, len(nums)):
curr = 1
for j in range(0, i):
if nums[j] < nums[i]:
curr = max(curr, dp[j] + 1)

dp[i] = curr
res = max(res, curr)

return res

class Solution:
def find_index(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1

while left + 1 < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid
else:
right = mid

return right

def lengthOfLIS(self, nums: List[int]) -> int:
sort = [float('inf')] * (len(nums) + 1)

for num in nums:
index = self.find_index(sort, num)
sort[index] = num

res = 0
for num in sort:
if num != float('inf'):
res += 1

return res