Longest Increasing Subsequence


  • 0

    Click here to see the full article post


  • 0

    Like the final solution


  • 0
    R

    how about this solution?
    0_1491533520389_2017-04-07 10-51-19屏幕截图.png


  • 0
    J

    Your english is very limited and makes the post hard to understand


  • 0
    K

    The English is hard to understand. Please paraphrase. For example, in Solution 3, please clearly say "dp[i] represents the longest subsequence ending exactly at i.".


  • 0
    0

    @kenteng Completely agree with you!
    For example, if the inputs nums is [4, 10, 4], the solution builds the following dp:
    [1, 2, 1]


  • 0
    K

    Note: dp array does not result in longest increasing subsequence, but length of dpdp array will give you length of LIS.
    This sentence makes me completely understands the binary dp solution.Thanks very much!


  • 0
    D

    Does this O(2^n) approach make sense ? Why simply use two loop O(n^2) for brute force? We can find all LIS start with every element in 2 loops. Am I right ?


  • 0
    H

    @danielz You don't simply compare two elements in each iteration. Think it in another way, the largest possible total number of the combination of the LIS is 2^n, and thus, the brute force takes O(2^n) to finish.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.