leetcode-go/medium/300.longest-increasing-subsequence.go

func lengthOfLISSlow(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return n
	}
	lis := make([]int, n) // DP, O(n^2) time complexity
	lis[0] = 1
	for i := 1; i < n; i *= 2 {
		copy(lis[i:], lis[:i])
	}
	max := 1
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] && lis[i] < lis[j]+1 {
				lis[i] = lis[j] + 1
				if max < lis[i] {
					max = lis[i]
				}
			}
		}
	}
	return max
}

func lengthOfLIS(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return n
	}
	lis := []int{nums[0]}
	max := 1
	for i := 1; i < n; i++ {
		if lis[max-1] < nums[i] {
			lis = append(lis, nums[i]) // O(nlog(n)), maintain the smallest LIS only
			max++
		} else {
			beg, end := 0, max
			for beg < end {
				mid := beg + (end-beg)/2
				if lis[mid] < nums[i] {
					beg = mid + 1
				} else if nums[i] < lis[mid] {
					end = mid
				} else {
					beg = mid
					break
				}
			}
			lis[beg] = nums[i]
		}
	}
	return max
}