vue3 最长递增子序列 diff优化

//vue3优化版（回头我会完善下算法思路）

function getSequence(arr) {

    const p = arr.slice()

    const result = [0]

    let i, j, u, v, c

    const len = arr.length

    for (i = 0; i < len; i++) {

        const arrI = arr[i]

        if (arrI !== 0) {

            j = result[result.length - 1]

            if (arr[j] < arrI) {

                p[i] = j

                result.push(i)

                continue

            }

            u = 0

            v = result.length - 1

            while (u < v) {

                c = ((u + v) / 2) | 0

                if (arr[result[c]] < arrI) {

                    u = c + 1

                } else {

                    v = c

                }

            }

            if (arrI < arr[result[u]]) {

                if (u > 0) {

                    p[i] = result[u - 1]

                }

                result[u] = i

            }

        }

    }

    u = result.length

    v = result[u - 1]

    while (u-- > 0) {

        result[u] = v

        v = p[v]

    }

    return result

}

console.log(getSequence([10, 9, 2, 5, 3, 7, 101, 18]));

//算法原型——基础算法版

//Objective is to find the longest increasing subsequence in an array.

let nums = [10,9,2,5,3,7,101,18]

//O(n^2) solution that uses dynamic programming to figure out if we want the

//element in the subsequence or not.

if (nums.length == 0) {

    return 0

}

//Every element initially starts with a subsequence of length 1

let dp = new Array(nums.length).fill(1)

//Use a nested iterator to compare all pairs of elements in the array

for (let i = 0; i < nums.length; i++) {

    for (let j = 0; j < i; j++) {

        //If nums[i] = 5 && nums[j] = 2, then we can choose to add

        //the previous subsequence to the current one

        if (nums[i] > nums[j]) {

            dp[i] = Math.max(dp[i], dp[j] + 1)

        }

    }

}

return Math.max(...dp)

巴特西

vue3 最长递增子序列 diff优化

最新文章

热门文章