最长上升子序列

发表于 分类于 阅读次数：

最长上升子序列（难度：中等）

1

方法：动态规划

2
3
4

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==0)
            return 0;
        int[] dp = new int[nums.length];
        int ans = 1;
        for(int i = 0; i < nums.length; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
5
进阶：将时间复杂度降低到O(nlogn)。 使用贪心算法+二分查找