leetcode-最长上升子序列(300)

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

示例:

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

思路

dp[n]表示以nums[n]结尾的最长上升子序列；

dp[n]=dp[往前走小于nums[n]的数] 中最大的值 + 1；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int lengthOfLIS(int[] nums) {
        //dp[n]=dp[往前走小于nums[n]的数]中最大的值+1；
        int len=nums.length;
        if(len==0){
            return 0;
        }
        int re =1;
        int []dp =new int[len];
        for(int i = 0;i<len;i++){
            dp[i]=1;
            int temp = nums[i];
            int index=i;
            index--;
            while(index>=0){
                if(nums[index]<temp){
                    dp[i]=Math.max(dp[index]+1,dp[i]);
                }
                index--;
            }
            re = (re < dp[i] ? dp[i] : re);
        }
        return re;
    }
}