題目：最長上升子序列
給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
示例：
輸入: [10,9,2,5,3,7,101,18]輸出: 4解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。
說明:
可能會有多種最長上升子序列的組合，你只需要輸出對應(yīng)的長度即可。
你算法的時間復雜度應(yīng)該為 O(n2) 。
分析
動態(tài)規(guī)劃問題，用dp[i]表示以第i個數(shù)字結(jié)尾的最長上升子序列的長度，第i個數(shù)字一定要被選取，則有
dp[i]=max(dp[j])+1; 0<=j<i且nums[i]>nums[j]則整個數(shù)組的最長子序列長度為max(dp[i]); 0<=i<n
代碼
class Solution {public:int lengthOfLIS(vector<int>& nums) {if (nums.empty()) return 0;vector<int> dp(nums.size(), 0);for (int i = 0, size = nums.size(); i < size; ++i) {dp[i] = 1;for (int j = 0; j < i; ++j) {if (nums[i] > nums[j]) {dp[i] = max(dp[i], dp[j]+1);}}}return *max_element(dp.begin(), dp.end());}};