leetcode300. 最长递增子序列

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

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

思路

初始状态 dp[i] 全为1，表示最长子序列长度

遍历 nums[i]

        遍历 j < i nums[j]

                当 nums[i] > nums[j] , 最长上升子序列长度为 dp[j]+1

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int result =0;
        if(nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for(int i = 0 ; i< nums.length; i++){
            for(int 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;
    }
}