300. Longest Increasing Subsequence

// nums: [10,9,2,5,3,7,101,18]
// 输出: 4

// dp[i] 定义为 nums[0..i-1] 最长递增子序列的长度。
// 状态方程: dp[i]=max(dp[i], dp[j]+1) (j=0,1,2,...,i-1), 且 nums[i]>nums[j]
// 初始化: 求最长递增子序列, 最少为1, 所以dp[i]=1  (i=0,1,2,...,n-1)

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