Leetcode: Longest Increasing Subsequence

Longest Increasing Subsequence


<a href=”https://github.com/dennyzhang/code.dennyzhang.com/tree/master/problems/longest-increasing-subsequence“><img align=”right” width=”200″ height=”183″ src=”github.png” /></a>

Similar Problems:


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.

Follow up: Could you improve it to O(n log n) time complexity?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/longest-increasing-subsequence
// Basic Ideas: dynamic programming
//    dp(i): ends with nums[i]
// Complexity: Time O(n*n), Space O(n)
func lengthOfLIS(nums []int) int {
    res := 0
    l := make([]int, len(nums))
    for i, num := range nums {
        l[i] = 1
        if i != 0 {
            for j:=i-1; j>=0; j-- {
                if nums[j] < num {
                    if l[j] + 1 > l[i] {
                        l[i] = l[j]+1
                    }
                }
            }
        }
        if l[i] > res { res = l[i] }
    }
    return res
}

<div style=”overflow: hidden;”>

<div style=”float: left; padding: 5px”> <a href=”https://www.linkedin.com/in/dennyzhang001“><img src=”linkedin.png” alt=”linkedin” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”github.png” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”slack.png” alt=”slack”/></a></div>

</div>


Share It, If You Like It.

Leave a Reply

Your email address will not be published.