# [leetcode] Longest Increasing Subsequence

Longest Increasing Subsequence

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(n2) complexity.

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

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

dynamic programming. O(n^2)

dp[i] is the longest increasing array including  nums[i]

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.