题解 | BM71 最长上升子序列(一)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 给定数组的最长严格上升子序列的长度。
 * @param arr int整型一维数组 给定的数组
 * @return int整型
 */
function LIS(arr) {
    // write code here
    let len = arr.length;
    let ans = new Array(len).fill(1);
    let max = 1;
    if (len < 1) {
        return [];
    }
    for (let i = 1; i < len; i++) {
        for (let j = 0; j < i; j++) {
            // 若j的值小于i的值并且在j的基础上加一大于累计最大长度
            if (arr[j] < arr[i] && ans[j] + 1 > ans[i]) {
                ans[i] = ans[j] + 1;
                if (ans[i] > max) {
                    max = ans[i];
                }
            }
        }
    }
    console.log("ans", ans);
    return max;
}
module.exports = {
    LIS: LIS,
};