算法: 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是什么意思。

假设有一帮人要形成一个集团，他们尽可能使集团人数最大，并且他们要在集团内按实力排位置。现在，他们一个个加入，进行友好的政治斗争。

斗争的规则很简单：

1. Arr[i] = j 代表着第i个人具有j大小的实力，这种实力是他斗争的筹码。
2. 最后形成的集团里，先来者不能管理后来者，他只能管理比他更早到的人。
3. 每个人到来的人都知道，想要成立人数为i的集团，那么要找谁当这个集团的老大。这个用M来记录。M[i] = j，形成人数为i的集团，那么需要让Arr[j]来担任集团长。
4. 每个人经历斗争后都知道，将来选择自己的下手，并使自己掌管的人达到最多，最好选择谁。这个通过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. 每组牌都是从大到小排列，小的牌不能放在大的牌上。
2. 放置牌时，从左至右查看，将牌放置能最左的能放置的组里，如果所有组都不能放置，那么这张牌在最右形成新的组。

假设数列是[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
    }, [])
}

最后

git上测试文件与代码