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
}