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 = nums
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
}``````