Meng

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example

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.

题意：给一个数组， 找出最长的上升子序列。 O(n^2)的解法比较直接， dp[i]就代表以当前index i对应数值为尾的最长的子序列的长度。 每次扫一遍 0～i-1，更新dp[i]就行了。

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length  < 1) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int ret = 1;
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
            ret = Math.max(dp[i], ret);
        }
        return ret;
    }
}

这道题其实还有 O(nlogn) 的解法，dp[i] 代表的是长度为i的子序列的结尾数值最小值 遍历整个数组，向维护一个递增的数列dp中插入当前值，维护的数列只有在当前值比所有数列里的值都大的情况才会增长， 不然的话会更新之前数列里面的值为相同长度但拥有更小的尾数。举例,

input: [0, 8, 4, 12, 2]
dp: [0]
dp: [0, 8]
//数列没有增长，因为 4 更新 8 变成了递增长度为2的尾数最小的值
dp: [0, 4]
dp: [0, 4, 12]

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for(int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if(i < 0) {
                i = - (i + 1);
            }
            dp[i] = num;
            if(i == len) len++;
        }
        return len;
    }
}

Note: Arrays.binarySearch() method returns index of the search key, if it is contained in the array, else it returns (-(insertion point) - 1). The insertion point is the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key

Gitalking ...

Search