Skip to content

最长递增子序列 #277

@Nasuke

Description

@Nasuke

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

参考代码如下:

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let n = nums.length, res = 0;
    let f = new Array(n).fill(1)

    for(let i = 0; i < n; i++)
        for(let j = 0; j <=i; j++){
            if(nums[j] < nums[i]){
                f[i] = Math.max(f[i], f[j] + 1)
            }
        }
    for(let i = 0; i < n; i++){
        res = Math.max(f[i],res)
    }
    return res
};

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions