300. Longest Increasing Subsequence

Problem

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n^2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Problem Summary

Given an unordered array of integers, find the length of the longest increasing subsequence.

Solution Ideas

• Given an integer sequence, find the length of the longest increasing subsequence in it. This problem is the classic LIS longest increasing subsequence problem.
• dp[i] represents the length of the longest increasing subsequence ending with the i-th number. Put another way, dp[i] represents the length of the longest increasing subsequence that can be obtained by choosing the number nums[i] within the range [0,i]. The state transition equation is dp[i] = max( 1 + dp[j]), where j < i && nums[j] > nums[i], taking the maximum value among all that satisfy the condition. Time complexity O(n^2)
• There is another faster solution to this problem. Consider this question: can we use an array to record the last number of an increasing subsequence? If this number is smaller, then the probability of adding numbers after this subsequence is higher, and it is more likely to become the longest increasing subsequence. For example: nums = [4,5,6,3], all of its increasing subsequences are

    len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
    len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
    len = 3   :      [4, 5, 6]            => tails[2] = 6

• What is stored in tails[i] is the smallest ending value among all increasing subsequences of length i + 1. It is also easy to prove that the values in the tails array must be increasing (because we describe the longest increasing subsequence using the ending number). Since tails is ordered, we can use binary search to update the values in this tail array. The update strategy is as follows: (1). If x is larger than all tails elements, then put it directly at the end and increase the length of the tails array by one; this corresponds to Solution 2, where the binary search cannot find the corresponding element value, so num is directly placed at the end of dp[]; (2). If tails[i-1] < x <= tails[i], update tails[i], because x is smaller and more capable of obtaining the longest increasing subsequence; this step corresponds to updating dp[i] to num in Solution 2. The final length of the tails array is the longest increasing subsequence. The time complexity of this approach is O(n log n).
• This problem is a one-dimensional LIS problem. The two-dimensional LIS problem is Problem 354. The three-dimensional LIS problem is Problem 1691.

Code

package leetcode

import "sort"

// Solution 1 O(n^2) DP
func lengthOfLIS(nums []int) int {
	dp, res := make([]int, len(nums)+1), 0
	dp[0] = 0
	for i := 1; i <= len(nums); i++ {
		for j := 1; j < i; j++ {
			if nums[j-1] < nums[i-1] {
				dp[i] = max(dp[i], dp[j])
			}
		}
		dp[i] = dp[i] + 1
		res = max(res, dp[i])
	}
	return res
}

// Solution 2 O(n log n) DP
func lengthOfLIS1(nums []int) int {
	dp := []int{}
	for _, num := range nums {
		i := sort.SearchInts(dp, num)
		if i == len(dp) {
			dp = append(dp, num)
		} else {
			dp[i] = num
		}
	}
	return len(dp)
}