**Tags**

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

For example,

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(*n ^{2}*) complexity.

**Follow up:** Could you improve it to O(*n* log *n*) time complexity?

**Solution 1:** dynamic programming solution. use dp[i] to indicate longest increasing subsequence end at i. so for each item i, scan all the previous dp[j] and find the max dp[j] + 1 where nums[j] < nums[i].

public int LengthOfLIS(int[] nums) { if (nums == null || nums.Length == 0) return 0; var dp = new int[nums.Length]; 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], dp[j] + 1); } } } return dp.Max(); }

**Solution 2**: see here for explanation.

public int LengthOfLIS(int[] nums) { if (nums == null || nums.Length == 0) return 0; var orderednum = new List(); foreach (var num in nums) { var index = orderednum.BinarySearch(num); if (index < 0) index = -(index + 1); if(index == orderednum.Count) orderednum.Add(num); else orderednum[index] = num; } return orderednum.Count; }