Longest Increasing Subsequence

FullStackDeveloper 发布于2019-08-14 17:23 / 1724人阅读

摘要：题目链接主要两种方法和用，就是每次找出为结尾的最长的串的长度就好了。所以分解成就是，这个复杂度是。用一个数组，表示的长度为，表示长度为的，最右边的可能的最小值。这里只要求长度即可，那就直接用就可以了，整个用个数组就行了。

Longest Increasing Subsequence

题目链接：https://leetcode.com/problems...

主要两种方法：dp和greedy

dp：用dp table，就是每次找出nums[i]为结尾的最长的increasing串的长度就好了。所以分解成subproblem就是: dp[i] = max(dp[j]) + 1，这个复杂度是O(N^2)。

然后就是greedy + binary search的方法，改进NlogN。用一个数组min[i]，i表示increasing sequence的长度为i，min[i]表示长度为i的increasing sequence，最右边的num可能的最小值。整个是patient sort的思路。
http://www.cs.princeton.edu/c...

stack的top元素按从小到大的顺序所以可以binary search。如果允许重复且重复的算在increasing sequence里面，那么重复的element就加到比它大的那个top下面就好了。如果重复的不算的话，就每次找>=的地方，查一下是否是重复，是就不加，不是就往里面加。
如果求路径就加个parent point的辅助数组。这里只要求长度即可，那就直接用top（min）就可以了，整个用个数组就行了。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        /* greedy + binary search
         * min[i]: minimum rightmost element in increasing sequence with length = i + 1
         */
         int[] min = new int[nums.length+1];
         min[0] = nums[0];
         int index = 0;
        for(int i = 1; i < nums.length; i++) {
            // new one >= rightmost one, increase the length of sequence
            if(nums[i] > min[index]) {
                min[++index] = nums[i];
            }
            // new one < leftmost, update the leftmost
            else if(nums[i] <= min[0]) {
                min[0] = nums[i];
            }
            // new one between [0, index + 1], find the place k that
            // min[k-1] < nums[i] <= min[k], update min[k]
            else {
                int k = binarySearch(min, nums[i], 0, index);
                min[k] = nums[i];
            }
        }
        return index + 1;
    }
    
    private int binarySearch(int[] min, int x, int l, int r) {
        while(l + 1 < r) {
            int mid = l + (r - l) / 2;
            if(min[mid] >= x) r = mid;
            else l = mid;
        }
        if(min[l] >= x) return l;
        return r;
    }
}

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

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

[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
Longest Increasing Subsequence

摘要：解题思路求不必连续的最长升序字符串长度，采用动态规划，利用状态表示以字符结尾的最长子串的长度，那么状态转移方程就是且必须小于另外还需维护一个最大长度。 Longest Increasing SubsequenceGiven an unsorted array of integers, find the length of longest increasing subsequence. ...

yangrd 2019-08-16 10:27 评论0 收藏0
[LeetCode] 300. Longest Increasing Subsequence

Problem 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...

luckyyulin 2019-08-19 11:13 评论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
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