# 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=”” /></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;”>