动态规划6：最长上升子序列

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

分析可知，该问题具有最优子结构。即选定中间一个数字，由它结尾的LIS只和前面的数字有关。

定义状态 f(n)为以第n为元素为结尾的最长上升子序列长度。

状态转义： f(n) = 满足arr[i] < arr[n]时 所有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);