[leetcode]300. Longest Increasing Subsequence最长递增子序列

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?

 

Solution: DP

dp[i] stands for the length of LIS ends with nums[i] (nums[i] must be used)

-->

 

-->

 

-->-->

 

 

code

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

 

转载于:https://www.cnblogs.com/liuliu5151/p/9841060.html