成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

[LintCode] Longest Increasing Subsequence

Flands / 2638人閱讀

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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64973.html

相關(guān)文章

  • [Lintcode] Longest Increasing Subsequence 最長(zhǎng)上升序列

    摘要：樣例給出，這個(gè)是，返回給出，這個(gè)是，返回挑戰(zhàn)要求時(shí)間復(fù)雜度為或者說(shuō)明最長(zhǎng)上升子序列的定義最長(zhǎng)上升子序列問(wèn)題是在一個(gè)無(wú)序的給定序列中找到一個(gè)盡可能長(zhǎng)的由低到高排列的子序列，這種子序列不一定是連續(xù)的或者唯一的。 Longest Increasing Subsequence 本文最新版本位于 https://yanjia.me/zh/2018/11/... 給定一個(gè)整數(shù)序列，找到最長(zhǎng)上升子序...

    hlcc 評(píng)論0 收藏0

  • [LintCode] Longest Increasing Continuous Subseque

    摘要：最長(zhǎng)連續(xù)遞增遞減子序列，設(shè)置正向計(jì)數(shù)器，后一位增加則計(jì)數(shù)器加，否則置。反向計(jì)數(shù)器亦然。每一次比較后將較大值存入。 Problem 最長(zhǎng)連續(xù)遞增／遞減子序列 Give an integer array，find the longest increasing continuous subsequence in this array.An increasing continuous subs...

    wwq0327 評(píng)論0 收藏0

  • Longest Increasing Subsequence

    摘要：解題思路求不必連續(xù)的最長(zhǎng)升序字符串長(zhǎng)度，采用動(dòng)態(tài)規(guī)劃，利用狀態(tài)表示以字符結(jié)尾的最長(zhǎng)子串的長(zhǎng)度，那么狀態(tài)轉(zhuǎn)移方程就是且必須小于另外還需維護(hù)一個(gè)最大長(zhǎng)度。 Longest Increasing SubsequenceGiven an unsorted array of integers, find the length of longest increasing subsequence. ...

    yangrd 評(píng)論0 收藏0

  • Longest Increasing Subsequence

    摘要：題目鏈接主要兩種方法和用，就是每次找出為結(jié)尾的最長(zhǎng)的串的長(zhǎng)度就好了。所以分解成就是，這個(gè)復(fù)雜度是。用一個(gè)數(shù)組，表示的長(zhǎng)度為，表示長(zhǎng)度為的，最右邊的可能的最小值。這里只要求長(zhǎng)度即可，那就直接用就可以了，整個(gè)用個(gè)數(shù)組就行了。 Longest Increasing Subsequence 題目鏈接：https://leetcode.com/problems... 主要兩種方法：dp和gree...

    FullStackDeveloper 評(píng)論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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<