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(

n) complexity.^{2}

Follow up:Could you improve it to O(nlogn) 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; } };