算法: Longest increasing subsequen
定义
Longest increasing subsequence(lis)算法是为了找到一个数列里最长的递增子串。
lis(array) -> longest increasing subseq of array
lis([1, 3, 4, 2, 6, 5, 7]) -> [1, 3, 4, 6, 7]
lis([5, 2, 1, 3, 4, 7, 8, 6, 9]) -> [2,3,4,7,8,9]
暴力解法
总体思路
function lis(arr) {
findAllSubseq(arr) // 找到所有的子串
.filter((subseq) => checkMonotonic(subseq)) // 过滤所有不单调递增的子串
.reduce((ret, cur) => { //找到最长的单调递增子串
cur.length > ret.length ? ret = cur: ret
return ret
})
}
找到所有的子串
对于[1,2,3],其拥有的非空子串包括[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]共7个,对于一个长度为n的数列，它的非空子串个数为2^n-1。
这是最简单的排列组合,给定一个子串,对于数列中每一个数,它只有两种可能,要么在子串中,要么不在子串中。
使用二进制数表示[1,2,3]的所有非空子串
| binary presentation | subseq |
|---|---|
| 001 | [1] |
| 010 | [2] |
| 100 | [3] |
| 011 | [1,2] |
| 101 | [1,3] |
| 110 | [2,3] |
| 111 | [1,2,3] |
每一个子串都对应了一个数的二进制表示
利用上面的发现我们可以编写找出所有子串的函数（空子串没有影响）
function findAllSubseq(arr) {
var len = arr.length
var ret = []
var i, j
for (i = 1; i < Math.pow(2, len); i++) {
var _temp = [];
for (j = 0; j < len; j++) {
if (i & (1 << j)) {
_temp.push(arr[j]);
}
}
ret.push(_temp)
}
return ret
}
验证子串的单调递增性
很容易实现，这里用map模拟了zip
function checkMonotonic(arr){
return arr.map((val, idx, arr) => [val, arr[idx-1]])
.every((val) => val[1] ? val[1] < val[0] : true)
}
LIS暴力破解
function lisDumb(arr) {
return findAllSubseq(arr)
.filter((val) => checkMonotonic(val))
.reduce((ret, cur) => {
cur.length > ret.length ? ret = cur: ret
return ret},[])
}
暴力破解的增长级别是O(2^n),效率低得可怕。
WIKI推荐解法
解决LIS问题，一般采用wiki推荐的方法,这个算法利用了二分查找算法和链表数据结构,最终的增长级别与快排相同,都是O(nlogn)。
非专业解释
wiki推荐的算法很像patience sorting，但是实现得更复杂。要理解wiki推荐的这个算法，关键是理解M和P是什么意思。
假设有一帮人要形成一个集团，他们尽可能使集团人数最大，并且他们要在集团内按实力排位置。现在，他们一个个加入，进行友好的政治斗争。
斗争的规则很简单：
-
Arr[i] = j代表着第i个人具有j大小的实力，这种实力是他斗争的筹码。 - 最后形成的集团里，先来者不能管理后来者，他只能管理比他更早到的人。
- 每个人到来的人都知道，想要成立人数为
i的集团，那么要找谁当这个集团的老大。这个用M来记录。M[i] = j，形成人数为i的集团，那么需要让Arr[j]来担任集团长。 - 每个人经历斗争后都知道，将来选择自己的下手，并使自己掌管的人达到最多，最好选择谁。这个通过
P来记录，P[i] = j，第i个人将来担任位置，那么他将选择第j个来的人当他的下手。第j个人在第0～i-1号人里，能召集最多的人。
import search from './binarySearch.js'
export default (arr)=>{
var M = []
var P = arr.slice(0)
// 一个个到来，进行斗争
arr.forEach((val,idx,arr) => {
// 现在这里最大的集团人数为length，leader代表着最大集团的集团长
let leader = M[M.length-1]
// 看看这里最大集团的集团长
if (leader !== undefined) {
// 有，看看新来的人和这位集团长谁厉害
if (val > arr[leader]) {
// 新来的人厉害，他直接选择那位集团长成为他未来的最佳下手
// 他成为了更大集团的集团长
M.push(idx)
P[idx] = leader
return
}
} else {
// 没有，这里没有集团，新来的人自己建立一个集团
M.push(idx)
P[idx] = undefined
return
}
// 不用放弃，还有机会
// 他用二分法，查看自己在所有集团（人数从1到length）的集团长中的实力排行
// 0 | arr[M[0]] | 1 | arr[M[1]] | 2 | arr[M[3]] | 3 | arr[M[3]] | ...
// 如果他最菜，那么返回0
// 如果他仅次于最大人数集团的集团长，那么返回length
// 如果他比M[i]厉害，却比M[i+1]弱，那么返回i
// 这个算法的精妙之处在于arr[M[i]]序列是递增的，所有可以使用二分查找
let replaceIdx = search(M.reduce((pre,cur)=>{
pre.push(arr[cur])
return pre
}, []), val)
// 找到了他的位置，那么他就要取代这个位置上的人了
// 因为他与M[replaceIdx] 的人一样，可以管理同样多的人，但是他比M[replaceIdx]的人弱
// 让他来当这个人数集团的集团长，有利于后来的扩张
// 他让replaceIdx-1人数的集团长做他未来的最佳下手
P[idx] = P[M[replaceIdx]]
// 取代M[replaceIdx]上的人
M[replaceIdx] = idx
return
})
// 所有斗争完毕，最大的集团有lisLength人数
var lisLength = M.length
// 应该找Arr[leader]做集团长
var leader = M[lisLength - 1]
// 每个人都找寻自己的最佳下手，直到最后一个没有最佳下手的人
for (; lisLength > -1; lisLength--) {
M[lisLength] = leader
// 找寻最佳下手
leader = P[leader]
}
// 去除undefined
return M.slice(1)
}
Patience Sorting
使用patience sorting来寻找lis是最容易的方法，无论是从理解，还是实现上看。
patience sorting的讲解在Princeton的讲解里被描述地很清楚。
诡异的思路
假设数列是一组牌，每次都抽取一张，按规则放置，最后形成几组牌，每组牌都从大到小排列，组数对应这个数列lis的长度，每组第一张牌形成lis。
规则是：
- 每组牌都是从大到小排列，小的牌不能放在大的牌上。
- 放置牌时，从左至右查看，将牌放置能最左的能放置的组里，如果所有组都不能放置，那么这张牌在最右形成新的组。
假设数列是[1,3,5,0,4,2,7,6,8,9]
每次放置牌时，组的结果如下:
init: [ ]
0: [ [1] ] 序号0代表放置完第0张牌
1: [ [1], [3] ]
2: [ [1], [3], [5] ]
3: [ [1, 0], [3], [5]]
4: [ [1, 0], [3], [5, 4]]
5: [ [1, 0], [3, 2], [5, 4]]
6: [ [1, 0], [3, 2], [5, 4], [7]]
7: [ [1, 0], [3, 2], [5, 4], [7, 6]]
8: [ [1, 0], [3, 2], [5, 4], [7, 6], [8] ]
9: [ [1, 0], [3, 2], [5, 4], [7, 6], [8], [9]]
一共6组，代表该数列lis长度为6。
取每个组的第一个数形成[1,3,5,7,8,9]，这是该数列的最长递增子串。
实现patience sorting也非常简单
patience sorting实现
// patience sorting
export default (arr) => {
return arr.reduce((ret, cur, idx, arr) => {
let lo = 0
let hi = ret.length
while(lo <= hi) {
let mid = ((lo + hi) / 2) | 0
let pile = ret[mid] || []
if (cur >= pile[pile.length - 1]) {
lo = mid + 1
} else {
hi = mid - 1
}
}
let insertIdx = lo
if (insertIdx === ret.length) {
ret.push([cur])
} else {
ret[insertIdx].push(cur)
}
return ret
}, [])
}
LIS实现
import pSort from './patienceSorting.js'
export default (arr) => {
var piles = pSort(arr)
return piles.reduce((ret, cur) => {
ret.push(cur[0])
return ret
}, [])
}
