300. Longest Increasing Subsequence

source: https://leetcode.com/problems/longest-increasing-subsequence/

Question

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

思路

从dp的思路出发，这个问题有两点比较难想到：

• dp[n]数组代表的意义，一开始的思路是作为以这个数开始的最大递增子序列，没想到是以这个数结尾的最大递增子序列
• 状态转移的方式， 是要去前面的所有数组里去做比对，符合最大的意义

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
    const dp = [];
    dp[0] = 1;
    let ret = dp[0];
    for (let i = 1; i < nums.length; i++) {
        dp[i] = dp[0];
        dp.forEach((v, index) => {
            if (nums[index] < nums[i]) dp[i] = Math.max(v + 1, dp[i]);
        });
        ret = Math.max(dp[i], ret);
    }
    return ret;
};

总结

有些问题即使提前知道要用dp来做，但是实际找出dp数组的意义和状态转移的方式还是很难，即如何拆分成更细的子问题，需要更多的做题经验。