每日一题：最长上升子序列

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
复制

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());
  }
};
复制