LeetCode : 300. Longest Increasing Subsequence 最长上升子序列

忘是亡心i 2021-06-24 16:11 501阅读 0赞

**试题**  
Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: \[10,9,2,5,3,7,101,18\]  
Output: 4  
Explanation: The longest increasing subsequence is \[2,3,7,101\], therefore the length is 4.  
Note:

There may be more than one LIS combination, it is only necessary for you to return the length.  
Your algorithm should run in O(n2) complexity.  
Follow up: Could you improve it to O(n log n) time complexity?  
**代码**  
dp以当前位置为结尾的最长子序列。

class Solution {
        public int lengthOfLIS(int[] nums) {
            if(nums==null || nums.length==0) return 0;
            int len = nums.length;
            int max = 0;
            int[] dp = new int[len];
            
            for(int i=0; i<len; i++){
                for(int j=0; j<i; j++){
                    if(nums[i]-nums[j]>0){
                        dp[i] = Math.max(dp[j]+1,dp[i]);
                    }
                }
                max = Math.max(max, dp[i]);
            }
            return max+1;
        }
    }

LeetCode : 300. Longest Increasing Subsequence 最长上升子序列

发表评论取消回复

还没有评论，来说两句吧...

相关阅读