1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

// @Title: 最长递增子序列 (Longest Increasing Subsequence)
// @Author: 15816537946@163.com
// @Date: 2019-11-20 17:42:29
// @Runtime: 0 ms
// @Memory: 2.3 MB
/*
 * @lc app=leetcode.cn id=300 lang=golang
 *
 * [300] 最长上升子序列
 *
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/description/
 *
 * algorithms
 * Medium (43.23%)
 * Likes:    269
 * Dislikes: 0
 * Total Accepted:    24.7K
 * Total Submissions: 57.2K
 * Testcase Example:  '[10,9,2,5,3,7,101,18]'
 *
 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
 *
 * 示例:
 *
 * 输入: [10,9,2,5,3,7,101,18]
 * 输出: 4
 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
 *
 * 说明:
 *
 *
 * 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
 * 你算法的时间复杂度应该为 O(n^2) 。
 *
 *
 * 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
 *
 */
 /*
func lengthOfLIS(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return n
	}

	lowest := make([]int, n)
	lowest[0] = nums[0]
	length := 1
	for i := 1; i < n; i++ {
		if nums[i] > lowest[length-1] {
			lowest[length] = nums[i]
			length++
		} else {
			j := binarySearch(lowest, nums[i], length)
			lowest[j] = nums[i]
		}
	}

	return length

}

func binarySearch(nums []int, target, n int) int {
	lo, hi := 0, n
	for lo < hi {
		mid := (lo + hi) >> 1
		if target > nums[mid] {
			lo = mid + 1
		} else {
			hi = mid
		}
	}

	return hi
}




func lengthOfLIS(nums []int) int {
	// 初始化tails[i]，全部设置为0
	tails := make([]int, len(nums), len(nums))
	l := 0
	// 遍历nums
	for _, x := range nums {
		// if nums[i] > dp[len-1]: len++, dp[len]=nums[i]
		idx := BinarySearch(tails, 0, l, x)
		tails[idx] = x
		if idx == l {
			l++
		}
        // fmt.Printf("x: %v, dp: %v\n", x, tails)
	}

	return l
}

// BinarySearch 搜索[first, last)区间，左闭右开，这是二分法的标准写法。
// first和last最后会在同一个下标。
// 搜索的是lower_bound，比如[1,2,3,3]，first和last最后会停在2后面的第一个3。
// 如果找不到，会返回大于value的最近下标。比如[1,3,3]，搜索2，得到的是第一个3的下标，搜索4，得到的是最后1个3后面的下标。
func BinarySearch(nums []int, first, last, value int) int {
	for first < last {
		mid := first + (last-first)/2
		if nums[mid] < value {
			first = mid + 1
		} else {
			last = mid
		}
	}
	return first
}
*/

func lengthOfLIS(nums []int) int {
	// tails := make([]int, 0, len(nums))
	
	tails := make([]int, len(nums), len(nums))
	var l int

	for _, v := range nums {
		idx := binarySearch(tails, 0, l, v)
		tails[idx] = v
		if idx == l {
			l++
		}
	}

	return l
}

func binarySearch(nums []int, lo, hi, target int) int {
	for lo < hi {
		mid := lo + (hi-lo)/2

		if nums[mid]< target {
			lo = mid+1
		} else {
			hi =mid
		}
	}

	return hi

}