leetcode最长递增子序列

在本题中，我们需要返回一个最长的子序列的长度。我们依旧可以使用动态规划的思想来做，不断改变dp数组的状态从而获得最后的结果。
dp数组定义：dp[i]表示以nums[i]结尾，此时最长递增子序列的长度。

递推公式：假设两个索引i和j，jnums[j]，可以说明，以nums[i]结尾的子序列，其递增子序列的长度是dp[j]+1，因为nums[i]>nums[j]。dp[j]后面至少还有一个数符合要求，所以是dp[j]+1。而我们要比较的就是max(dp[i]，dp[j]+1)。

初始化：dp[0]表示以nums[0]开头的子序列，其本身就是一个递增子序列，此时dp[0]=1。事实上，整个dp数组都应该初始化为1。考虑最坏的情况，整个序列是个严格递减的序列，那么以nums[i]结尾的子序列，其dp[i]=1。因为其本身就是一个符合要求的子序列。

遍历顺序：我们是要两个索引，都从前往后遍历，并且j要小于i，这时候才能比较nums[i]和nums[j]的关系。如果nums[i]>nums[j]。此时采用递推公式。

打印数组：我们打印出来的dp数组是表示包含nums[i]在内的最长子序列的长度，但不一定是整个数组最长子序列的长度，比如题中的第一个例子，就不包含nums[nums.length-1]。所以我们需要的是整个dp数组内的最大值。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 0;
        Arrays.fill(dp, 1);
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16