[leetcode]Longest Increasing Subsequence

wow_worktile 发布于2019-08-14 16:52 / 517人阅读

摘要：对于一个递增子序列，想要增加它的长度，就必须在尾部添加一个更大的值。表示以结尾的最长递增序列的长度。长度增加的条件就是一个数字比大。长度最大值即为输入数组的长度。

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n^2) complexity.

对于一个递增子序列，想要增加它的长度，就必须在尾部添加一个更大的值。
O(n^2)
dp[i]表示以nums[i]结尾的最长递增序列的长度。长度增加的条件就是一个数字比nums[i]大。

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

O(nlogn)
长度最大值即为输入数组的长度。用dp[i]表示，长度为i时，结尾的数字。可以不断更新。这里可以用binarySearch来查询需要插放的位置。
Java自带的binarySearch，如果有该元素则返回正确的index,如果没有返回-(index+1)，是一个负数，我们需要替换成正确的数值。

public class Solution {
    public int lengthOfLIS(int[] nums) {            
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
}

GPU云服务器云服务器 Increasing Subsequence Longest Leetcod

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

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

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

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 300. Longest Increasing Subsequence

摘要：题目要求找到整数数组中最长的递增子数组。该子数组可以为不连续的。如题目中例子所示，得到的最长子数组为。最后我们还需要遍历一遍全部子数组的长度并获得最大的长度。题目要求 Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [...

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

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

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

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

FullStackDeveloper 2019-08-14 17:23 评论0 收藏0