package DP
import "math"
// lengthOfLIS: 求最长递增子序列长度
// 时间复杂度: O(n * log n), 空间复杂度: O(n) <最优解>
func lengthOfLIS(nums []int) int {
size := len(nums)
dp := make([]int, size)
// dp[i]: 以i位置作为结尾的最长递增子序列长度
ends := make([]int, 0)
// ends[i]：长度为i+1的递增子序列的最小结尾
ans := math.MinInt
for i := 0; i < size; i++ {
pos := find(ends, nums[i])
if pos == len(ends) {
ends = append(ends, nums[i])
} else {
ends[pos] = nums[i]
}
dp[i] = pos + 1
ans = max(ans, dp[i])
}
return ans
}
// find: 在递增序列中找大于等于target的最左位置，不存在则返回size
func find(arr []int, target int) int {
ans := len(arr)
for left, right := 0, ans-1; left <= right; {
mid := left + (right-left)/2
if arr[mid] >= target {
ans = mid
right = mid - 1
} else {
left = mid + 1
}
}
return ans
}