[300] Longest Increasing Subsequence

 1 class Solution {
 2 public:
 3     int lengthOfLIS(vector<int>& nums) {
 4     
 5         if( nums.size() == 0 )
 6             return 0;
 7         
 8         // memo[i] 表示以 nums[i] 为结尾的最长上升子序列的长度 
 9         vector<int> memo(nums.size(),1);
10         for( int i = 1 ; i < nums.size() ; i ++ )
11             for( int j = 0 ; j < i ; j ++ )
12                 if( nums[j] < nums[i] )
13                     memo[i] = max( memo[i] , 1 + memo[j] );
14         
15         int res = 1;
16         for( int i = 0 ; i < nums.size() ; i ++ )
17             res = max( res, memo[i] );
18         
19         return res;            
20     }
21 };