有序列如下[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);
