Longest Increasing Subsequence

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 }