Longest Increasing Subsequence

来源：nineChapter

原帖：nineChapter; dp

题目：
Longest Increasing Subsequence
1 1000 2 3 4
10 11 12 1 2 3 4 13

代码：

 int longestIncreasingSubsequence(const vector<int> &nums) {  
   vector<int> dp(nums.size(), 0);  
   dp[0] = 1;  
   unordered_map<int, vector<int> > map;  
   map[0] = {nums[0]};  
   for (int i = 1; i < nums.size(); ++i) {  
     for (int j = 0; j < i; ++j) {  
       if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {  
         map[i] = move(map[j]);  
         map[i].push_back(nums[i]);  
         dp[i] = max(dp[i], dp[j] + 1);  
       }  
     }  
   }  
   for (auto i : map[nums.size()-1]) cout << i << " ";  
   cout << endl;   
   return dp[nums.size() - 1];  
 }  
   
 int main() {  
   vector<int> nums = {1,2,4,3,2,7,8,9};  
   longestIncreasingSubsequence(nums);  
   return 0;  
 }