刷题43——最长上升子序列

77.最长上升子序列

题目链接

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。

关键技术

动态规划

题目分析

1. 判断给定数组的长度，若长度为0，return 0;若长度为1，return 1;长度除这两种以外，计算最长上升子序列的长度；
2. 定义一个元素全为1，长度为给定数组长度的数组；定义max存放最长上升子序列的长度，并赋值为1；
3. 令dp[i]表示以num[i]这个元素作为上升子序列的最后的一个元素，所形成的最长上升子序列的最大长度；
4. 因为新的dp[i]（用dp[j]表示）的最长上升子序列的长度取决于nums[i]这个新的尾元素（用nums[j]表示），所以比较nums[ii]和nums[j]的大小；
5. 若nums[j] < nums[i]，那么dp[i] = Math.max(dp[i], dp[j]+1);
6. 比较max和dp[i]，取较大的值为最长上升子序列的长度。

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    if(nums.length === 0) return 0;
    else if(nums.length === 1) return 1;
    else{
        let dp = new Array(nums.length).fill(1);
        let max = 1;
        for(let i=0;i<nums.length;i++){
            for(let j=0;j<i;j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    } 
};