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?
解答： 对于数组中的数，维护一个vector ，里面保存的是对于每个i而言的最长在递增子串的长度。那么递增式就是对于每个dp[i]而言,都要遍历前面所有比他小的nums[i]值，然后所有的对应的dp值中取最大的那个，代表了前面的最长递增子串，再加1，作为目前的最长子串的长度。然后所有的dp[i]中最长那个就是结果。
class Solution { public: int lengthOfLIS(vector<int>& nums) { if(nums.size()==0) return 0; vector<int> dp(nums.size(),1); int res=0; for(int i=0;i<nums.size();i++) { for(int j=0;j<i ;j++) { if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1); } res=max(dp[i],res); } return res; } };