Longest Increasing Subsequence

LeetCode 300 · View on LeetCode

Find the length of the longest strictly increasing subsequence using the O(n log n) patience sorting approach with binary search.

package main

import (
	"fmt"
	"sort"
)

func lengthOfLIS(nums []int) int {
	tails := []int{}
	for _, n := range nums {
		pos := sort.SearchInts(tails, n)
		if pos == len(tails) {
			tails = append(tails, n)
		} else {
			tails[pos] = n
		}
	}
	return len(tails)
}

func main() {
	fmt.Println(lengthOfLIS([]int{10, 9, 2, 5, 3, 7, 101, 18})) // 4
	fmt.Println(lengthOfLIS([]int{0, 1, 0, 3, 2, 3}))            // 4
	fmt.Println(lengthOfLIS([]int{7, 7, 7, 7}))                   // 1
}