leetcode 300. Longest Increasing Subsequence

Seawolf

1. Given an unsorted array of integers, find the length of longest increasing subsequence.
   
2. 
   
3. Example:
   
4. 
   
5. Input: [10,9,2,5,3,7,101,18]
   
6. Output: 4
   
7. Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
   
8. Note:
   
9. 
   
10. There may be more than one LIS combination, it is only necessary for you to return the length.
    
11. Your algorithm should run in O(n2) complexity.
    
12. Follow up: Could you improve it to O(n log n) time complexity?

复制代码

dp solution

1. class Solution {
   
2. public:
   
3.     int lengthOfLIS(vector<int>& nums) {
   
4.         if(nums.size() == 0) return 0;
   
5.         int dp[nums.size()] = {0};
   
6.         dp[0] = 1;
   
7.         int max_ans = 0;
   
8.         for(int i = 0; i < nums.size();i++){
   
9.             int max1 = 0;
   
10.             for(int j = 0; j < i; j++){
    
11.                 if(nums[j] < nums[i]){
    
12.                     max1 = max(max1, dp[j]);
    
13.                 }
    
14.             }
    
15.             
    
16.             dp[i] = max1 +1;
    
17.             max_ans = max(max_ans,dp[i]);
    
18.         }
    
19.         
    
20.         return max_ans;
    
21.     }
    
22. };

复制代码