[Lintcode] Longest Increasing Subsequence 最长上升序列

hlcc 发布于2019-08-14 12:41 / 2522人阅读

摘要：样例给出，这个是，返回给出，这个是，返回挑战要求时间复杂度为或者说明最长上升子序列的定义最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。

Longest Increasing Subsequence 本文最新版本位于 https://yanjia.me/zh/2018/11/...

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。样例 给出[5,4,1,2,3]，这个LIS是[1,2,3]，返回 3
给出[4,2,4,5,3,7]，这个LIS是[4,4,5,7]，返回 4
挑战 要求时间复杂度为O(n^2) 或者O(nlogn)
说明 最长上升子序列的定义：
最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。
https://en.wikipedia.org/wiki...

动态规划法 复杂度

时间 O(N^2) 空间 O(N)

思路

由于这个最长上升序列不一定是连续的，对于每一个新加入的数，都有可能跟前面的序列构成一个较长的上升序列，或者跟后面的序列构成一个较长的上升序列。比如1,3,5,2,8,4,6，对于6来说，可以构成1,3,5,6，也可以构成2,4,6。因为前面那个序列长为4，后面的长为3，所以我们更愿意6组成那个长为4的序列，所以对于6来说，它组成序列的长度，实际上是之前最长一个升序序列长度加1，注意这个最长的序列的末尾是要小于6的，不然我们就把1,3,5,8,6这样的序列给算进来了。这样，我们的递推关系就隐约出来了，假设dp[i]代表加入第i个数能构成的最长升序序列长度，我们就是要在dp[0]到dp[i-1]中找到一个最长的升序序列长度，又保证序列尾值nums[j]小于nums[i]，然后把这个长度加上1就行了。同时，我们还要及时更新最大长度。

代码

public class Solution {
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        if(nums.length == 0){
            return 0;
        }
        // 构建最长升序序列长度的数组
        int[] lis = new int[nums.length];
        lis[0] = 1;
        int max = 0;
        for (int i = 1; i < nums.length; i++){
            // 找到dp[0]到dp[i-1]中最大的升序序列长度且nums[j]
比较好理解的版本
public class Solution {
    public int longestIncreasingSubsequence(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int[] lis = new int[nums.length];
        int max = 0;
        for (int i = 0; i < nums.length; i++){
            int localMax = 0;
            // 找出当前点之前的最大上升序列长度
            for (int j = 0; j < i; j++){
                if (lis[j] > localMax && nums[j] <= nums[i]){
                    localMax = lis[j];
                }
            }
            // 当前点则是该局部最大上升长度加1
            lis[i] = localMax + 1;
            // 用当前点的长度更新全局最大长度
            max = Math.max(max, lis[i]);
        }
        return max;
    }
}
耐心排序法
复杂度
时间 O(NlogN) 空间 O(N)
思路
在1,3,5,2,8,4,6这个例子中，当到6时，我们一共可以有四种
(1)不同长度
(2)且保证该升序序列在同长度升序序列中末尾最小
的升序序列
1
1,2
1,3,4
1,3,5,6
这些序列都是未来有可能成为最长序列的候选人。这样，每来一个新的数，我们便按照以下规则更新这些序列

如果nums[i]比所有序列的末尾都大，或等于最大末尾，说明有一个新的不同长度序列产生，我们把最长的序列复制一个，并加上这个nums[i]。
如果nums[i]比所有序列的末尾都小，说明长度为1的序列可以更新了，更新为这个更小的末尾。
如果在中间，则更新那个末尾数字刚刚大于等于自己的那个序列，说明那个长度的序列可以更新了。

比如这时，如果再来一个9，那就是第三种情况，更新序列为
1
1,2
1,3,4
1,3,5,6
1,3,5,6,9

如果再来一个3，那就是第二种情况，更新序列为
1
1,2
1,3,3
1,3,5,6

如果再来一个0，那就是第一种情况，更新序列为
0
1,2
1,3,3
1,3,5,6

前两种都很好处理，O(1)就能解决，主要是第三种情况，实际上我们观察直到6之前这四个不同长度的升序序列，他们末尾是递增的，所以可以用二分搜索来找到适合的更新位置。
注意
二分搜索时如果在tails数组中，找到我们要插入的数，也直接返回那个结尾的下标，虽然这时候更新这个结尾没有意义，但少了些判断简化了逻辑
代码
public class Solution {
public int longestIncreasingSubsequence(int[] nums) {
    // write your code here
    if(nums.length == 0){
        return 0;
    }
    // len表示当前最长的升序序列长度（为了方便操作tails我们减1）
    int len = 0;
    // tails[i]表示长度为i的升序序列其末尾的数字
    int[] tails = new int[nums.length];
    tails[0] = nums[0];
    // 根据三种情况更新不同升序序列的集合
    for(int i = 1; i < nums.length; i++){
        if(nums[i] < tails[0]){
            tails[0] = nums[i];
        } else if (nums[i] >= tails[len]){
            tails[++len] = nums[i];
        } else {
        // 如果在中间，则二分搜索
            tails[binarySearch(tails, 0, len, nums[i])] = nums[i];
        }
    }
    return len + 1;
}

private int binarySearch(int[] tails, int min, int max, int target){
    while(min <= max){
        int mid = min + (max - min) / 2;
        if(tails[mid] == target){
            return mid;
        }
        if(tails[mid] < target){
            min = mid + 1;
        }
        if(tails[mid] > target){
            max = mid - 1;
        }
    }
    return min;
}
}

云服务器 GPU云服务器最长递增子序列最长公共子序列 Increasing Subsequence

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64642.html

[LintCode] Longest Increasing Continuous Subseque

摘要：最长连续递增递减子序列，设置正向计数器，后一位增加则计数器加，否则置。反向计数器亦然。每一次比较后将较大值存入。 Problem 最长连续递增／递减子序列 Give an integer array，find the longest increasing continuous subsequence in this array.An increasing continuous subs...

wwq0327 2019-08-14 15:11 评论0 收藏0
[LintCode] Longest Increasing Subsequence

Problem Given a sequence of integers, find the longest increasing subsequence (LIS). You code should return the length of the LIS. Clarification Whats the definition of longest increasing subsequence?...

Flands 2019-08-14 14:22 评论0 收藏0
LeetCode[300] Longest Increasing Subsequence

摘要：再用二分法找当前值应该在排好序的数组中的插入位置。因为要找的是最长的序列，所以每次将排好序的数组中替换成已经排好序的，会能保证得到的结果是最长的。保证升序相等也要替换这个值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

blankyao 2019-08-14 15:01 评论0 收藏0
leetcode-300-Longest Increasing Subsequence

摘要：本质找出最长的递增子序列的长度，可以是不连续的。应用判断满足一定条件的子序列的最大长度，用动态数组加以处理。二分法确定满足条件的位置。类似二分法查找元素，查找某种情况的子序列。本质：找出最长的递增子序列的长度，可以是不连续的。用一个数组存储递增子序列，遍历原始数组，每增加一个数，往里添加到对应的顺序，记录他的位置，即为此数组的长度。成立的理由：每一个数添加以后，都有对...

amc 2019-07-30 17:36 评论0 收藏0
[leetcode]Longest Increasing Subsequence

摘要：对于一个递增子序列，想要增加它的长度，就必须在尾部添加一个更大的值。表示以结尾的最长递增序列的长度。长度增加的条件就是一个数字比大。长度最大值即为输入数组的长度。 Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10,...

wow_worktile 2019-08-14 16:52 评论0 收藏0