有序列如下[10,9,2,5,3,7,101,18,20]，求其LIS(Longest Increasing Sequence).

分析可知，該問題具有最優(yōu)子結(jié)構(gòu)。即選定中間一個(gè)數(shù)字，由它結(jié)尾的LIS只和前面的數(shù)字有關(guān)。

定義狀態(tài) f(n)為以第n為元素為結(jié)尾的最長上升子序列長度。

狀態(tài)轉(zhuǎn)義： f(n) = 滿足arr[i] < arr[n]時(shí) 所有i中 max{f(i)} + 1

function lis(arr) {
    const len = arr.length;
    let res = [];


    for(let i = 0; i<len; i++) {
        res[i] = 1;
        for(let j = i-1; j>=0; j--) {
            if(arr[i] > arr[j] && res[i]<res[j]+1 ) {
                res[i] = res[j] + 1;
            }
        }
    }

    return Math.max.apply(null, res);
}

const arr = [10,9,2,5,3,7,101,18,20];
lis(arr);