**Difficulty: Medium**

**Frequency: N/A**

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?

**Test Cases:**

**Solution 1:**

**Data structure:**

**Steps:**

**Complexity:**

**Code:**

class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if (!n) return 0; int result = 0; vector<int> dp(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1); } result = max(result, dp[i]); } return result; } };

**Solution 2:**

**Data structure:**

**steps:**

**Complexity**:

**Code**:

**Submission errors:**

**Things to learn:**