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,101], therefore the length is 4.
```

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

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

```
func lengthOfLIS(nums []int) int {
if nums == nil || len(nums) == 0 {
return 0
}
lenN := len(nums)
curLen := 0
lis := make([]int, lenN)
lis[0] = nums[0]
curLen++
for i:= 1; i < lenN; i++ {
if nums[i] > lis[curLen - 1] {
lis[curLen] = nums[i]
curLen++
}else{
pos := findPositionToReplace(lis, 0, curLen-1, nums[i])
lis[pos] = nums[i]
}
}
return curLen
}
func findPositionToReplace(nums []int, low, high, target int) int {
mid:= 0
for low <= high {
mid = (high + low) / 2;
switch {
case nums[mid] == target:
return mid;
case nums[mid] > target:
high = mid - 1
continue;
default:
low = mid+1
continue
}
}
return low
}
```