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

hlcc 發布于2019-08-14 12:41 / 2519人閱讀

摘要：樣例給出，這個是，返回給出，這個是，返回挑戰要求時間復雜度為或者說明最長上升子序列的定義最長上升子序列問題是在一個無序的給定序列中找到一個盡可能長的由低到高排列的子序列，這種子序列不一定是連續的或者唯一的。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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