題目：最長上升子序列
給定一個無序的整數數組，找到其中最長上升子序列的長度。
示例：
輸入: [10,9,2,5,3,7,101,18]輸出: 4解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。
說明:
可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。
你算法的時間復雜度應該為 O(n2) 。
分析
動態規劃問題，用dp[i]表示以第i個數字結尾的最長上升子序列的長度，第i個數字一定要被選取，則有
dp[i]=max(dp[j])+1; 0<=j<i且nums[i]>nums[j]則整個數組的最長子序列長度為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());}};