Longest Increasing Subsequence

Medium

The problem

A subsequence keeps some of the numbers in their original order, possibly skipping some. Return the length of the longest subsequence of nums in which every number is strictly bigger than the one before it.

Example 1
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
For example [2, 3, 7, 101].
Example 2
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
For example [0, 1, 2, 3].
Example 3
Input: nums = [7, 7, 7]
Output: 1
The numbers must strictly increase, so equal numbers do not chain.

Limits

1 ≤ len(nums) ≤ 2,500
-10,000 ≤ nums[i] ≤ 10,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Define the best sequence that ends exactly at position i. Which earlier elements can it extend?

The idea

dp[i] = 1 + max(dp[j]) for j<i with nums[j] < nums[i] (O(n²)); or keep a "tails" array and binary-search it (O(n log n)).

Target: O(n²), improvable to O(n log n)

Go function shape

func lengthOfLIS(nums []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// LengthOfLIS: length of the longest strictly increasing subsequence.
// State: dp[i] = best length ending exactly at nums[i].
func LengthOfLIS(nums []int) int {
	best := 0
	dp := make([]int, len(nums))
	for i := range nums {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		best = max(best, dp[i])
	}
	return best
}

Read the lesson: Dynamic Programming