未分類

Longest Increasing Subsequence

BinarySearch, DynamicProgramming, Go, LeetCode

Longest Increasing Subsequence

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

For example:

Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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?

提示 解題應用
DynamicProgramming 規律觀查
BinarySearch BinarySearch

Default:

1
2
3
func lengthOfLIS(nums []int) int {
}

解答思路:

這題如果沒有記錯的話似乎是很熱門的題目，總而言之看到的第一個想法就是先初始化一個相同長度的陣列，用來紀錄截至該數字時(從開頭到該數字的位置)能組出包含該數字的最長遞增子數列長度，如此一來後面取出的數字如果比前面的任一個大，只要將前面較小的值所對應到長度+1就”可能”會是到包含取出數字的最長遞增的子數列長度，因為比取出數字還小的元素可能不只1個，所以要在這些元素之中找出有著最大長度的子數列，最後待全數紀錄完畢後，紀錄陣列中的最大值就會是我們要的結果，程式碼如下(紀錄陣列中元素的初始長度皆為0，因此最後要記得在結果+1才做回傳):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if len(nums) == 0 {
	return 0
}
var max int
dp := make([]int, len(nums))
for i, _ := range nums {
	for j := 0; j < i; j++ {
		if nums[i] > nums[j] && dp[j]+1 > dp[i] {
			dp[i] = dp[j] + 1
		}
	}
}
for _, v := range dp {
	if v > max {
		max = v
	}
}
return max + 1

上面做法的時間複雜度是O(n^2)，然而題目進一步的希望時間複雜度能在O(nlogn)，這邊我就沒有想出來所以去看了討論區的解法，仔細觀查數列的話會發現越長的子數列，該數列最後一個值會越大，這似乎聽起來是理所當然，所以說只要紀錄截至取出的數字各個長度中子數列所能出現的最小尾巴值(數列的最後一個值)，最後紀錄的長度最多能到多少就會是我們要的結果，範例如下(假設數列為[4,5,6,3,4,7]):

1
2
3
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

接下來對於新取出的數字只要想成是在做類似插入排序的概念(找出最接近且比其大的值做取代，沒有比其大的值就將自身插在最後頭)就簡單多了，如果下一個取出的數字是4:

1
2
3
tails[0] = 3
tails[1] = 4
tails[2] = 6

再下一個取出的數字是7的話:

1
2
3
4
tails[0] = 3
tails[1] = 4
tails[2] = 6
tails[3] = 7  (紀錄的最大長度就會是最終的結果: 4)

總而言之這兩種方法最大的差異在於一個是紀錄截至取出的數字時包含該數字所能組出的最長子數列長度，另一個則是紀錄截至取出的數字時各個長度中子數列所能出現的最小尾巴值。

程式碼解說:

如思路結論所述就是每次將取出的數字想成是在做類似插入排序的概念(找出最接近且比其大的值做取代，沒有比其大的值就將自身插在最後頭)，最後紀錄的長度最多能到多少就會是我們要的結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var front int
var rear int
var mid int
var tails []int
for _, v := range nums {
	front = 0
	rear = len(tails)
	for front < rear {
		mid = (front + rear) / 2
		if v > tails[mid] {
			front = mid + 1
		} else {
			rear = mid
		}
	}
	if front == len(tails) {
		tails = append(tails, v)
	} else {
		tails[front] = v
	}
}
return len(tails)

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func lengthOfLIS(nums []int) int {
	var front int
	var rear int
	var mid int
	var tails []int
	for _, v := range nums {
		front = 0
		rear = len(tails)
		for front < rear {
			mid = (front + rear) / 2
			if v > tails[mid] {
				front = mid + 1
			} else {
				rear = mid
			}
		}
		if front == len(tails) {
			tails = append(tails, v)
		} else {
			tails[front] = v
		}
	}
	return len(tails)
}

總結:

有一未經排序的數列要找出最長遞增子數列的長度(詳細規則請看範例)，其做法共有兩種，一種是紀錄截至取出的數字包含該數字所能組出的最長子數列長度，另一種則是紀錄截至取出的數字各個長度中子數列所能出現的最小尾巴值，而兩種的時間複雜度分別為O(n^2)與O(nlogn)。

分享到