300. Longest Increasing Subsequence

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• 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