Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given
The longest increasing subsequence is
Given
[10, 9, 2, 5, 3, 7, 101, 18]
,The longest increasing subsequence is
[2, 3, 7, 101]
, therefore the length is 4
. Note that 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.
思路:double loop, j is element before i, dp[i] is current element seq max length eg[3,4,-1,0,6,2,3]
arr[j] < arr[i]: dp[i] is Max(dp[j]+1,dp[i])
//not update i if i already bigger(results from previous: 3,4,6; so not update when get to -1)
else not increaing: j++
once j=i: i++,j=0
//not update i if i already bigger(results from previous: 3,4,6; so not update when get to -1)
else not increaing: j++
once j=i: i++,j=0
Complexity: O(n^2)
public class Solution { public int lengthOfLIS(int[] nums) { if(nums.length<=1)return nums.length; int[]dp= new int[nums.length]; int max = 1; for(int i=0;i<dp.length;i++) dp[i]=1; for(int i=1;i<nums.length;i++){ for(int j=0;j<i;j++){ if(nums[j]<nums[i]){//increasing dp[i] = Math.max(dp[j]+1,dp[i]); max = Math.max(dp[i],max); } } } return max; } }
No comments:
Post a Comment