LeetCode 719. Find K-th Smallest Pair Distance

Problem

LeetCode 719. Find K-th Smallest Pair Distance

1. 题目简述

给出一个未排序的整形数组，返回其最长递增子序列的长度。

Input: [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. 

Note:

只需要长度，而不是具体的串

time complexity要在O(n ^ 2)以下

2. 算法思路

相关问题：

1. 673. Number of Longest Increasing Subsequence

首先要注意我们只需要返回长度即可，这里不需要考虑找出最长的那个子串，只要找到该串的长度即可。

暴力搜索

我们先来看看最暴力的思路，我们对每个节点记录一个dp值，该值表示从0到当前位置的数字中，以当前数字为结尾的最长递增子序列的长度。每次新到达一个数字后，找到其前面的所有数字中，比它小的所有数字中dp值最大的数字（不能等于，等于就不叫递增了），找出该节点的dp值，加一，即为当前节点的dp值。

$$dp[i] = max(dp[i], dp[j] + 1) (for j in 0 to n - 1 and nums[j] < nums[i])$$

时间复杂度为O(n ^ 2)，因为每次都要去找前面所有的数字，很慢。

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        int ret = 0;

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

        return ret;
    }
}