Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: 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(n2) complexity.Follow up: Could you improve it to O(n log n) time complexity?
=====================================================================
参考官方题解：https://leetcode.com/articles/longest-increasing-subsequence/
这个题是最长上升子序列问题。先在某一个位置，姑且用i来表示，然后，判断nums[i]是否比前面的i数大？如果大，那么再比较dp[i] 和 dp[j] + 1 哪个比较大（j就是前面的数字的下标）。
C++代码:
class Solution { public: int lengthOfLIS(vector<int>& nums) { if(nums.size() == 0) return 0; int n = nums.size(); vector<int> dp(n,1); //边界值就是1，因为无论如何LIS中的最小值就是1，否则就是0. int res = 1; for(int i = 1; i < n; i++){ for(int j = 0; j < i; j++){ if(nums[i] > nums[j] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1; } res = max(res,dp[i]); } return res; } };
转载于:https://www.cnblogs.com/Weixu-Liu/p/10846723.html
