[LintCode] Longest Increasing Subsequence

Flands 发布于2019-08-14 14:22 / 2564人阅读

Problem

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Clarification

What"s the definition of longest increasing subsequence?

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence"s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

https://en.wikipedia.org/wiki...

Example

For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [2, 4, 5, 7], return 4

Challenge

Time complexity O(n^2) or O(nlogn)

Solution DP O(n^2)

public class Solution {
    public int longestIncreasingSubsequence(int[] nums) {
        int n = nums.length, max = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                dp[i] = nums[i] >= nums[j] ? Math.max(dp[j]+1, dp[i]) : dp[i];
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}

Binary Search O(nlogn)

public class Solution {
    public int longestIncreasingSubsequence(int[] nums) {
        int n = nums.length, max = 0;
        if (n == 0) return 0;
        int[] tails = new int[nums.length];
        tails[0] = nums[0];
        int index = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < tails[0]) tails[0] = nums[i];
            else if (nums[i] >= tails[index]) tails[++index] = nums[i];
            else tails[bisearch(tails, 0, index, nums[i])] = nums[i];
        }
        return index+1;
    }
    public int bisearch(int[] tails, int start, int end, int target) {
        while (start <= end) {
            int mid = start + (end-start)/2;
            if (tails[mid] == target) return mid;
            else if (tails[mid] < target) start = mid+1;
            else end = mid-1;
        }
        return start;
    }
}

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

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

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

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

摘要：样例给出，这个是，返回给出，这个是，返回挑战要求时间复杂度为或者说明最长上升子序列的定义最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。 Longest Increasing Subsequence 本文最新版本位于 https://yanjia.me/zh/2018/11/... 给定一个整数序列，找到最长上升子序...

hlcc 2019-08-14 12:41 评论0 收藏0
[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
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
Longest Increasing Subsequence

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

FullStackDeveloper 2019-08-14 17:23 评论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