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

**Example:**

Input:`[10,9,2,5,3,7,101,18]`

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

## Solution

public class Solution { public int LengthOfLIS(int[] nums) { if(nums == null || nums.Length == 0) return 0; int[] LIS = Enumerable.Repeat(1,nums.Length).ToArray(); for(int i=0;i<nums.Length;i++) { for(int j=0;j<i;j++) { if(nums[i] > nums[j] && LIS[i] <= LIS[j]) { LIS[i] = 1 + LIS[j]; } } } //Find Max int max = LIS[0]; for(int i=1;i<LIS.Length;i++) max = Math.Max(LIS[i],max); return max; } }

Time Complexity: O(n*n)

Space Complexity: O(n)