C++刷leetcode（300. 最长上升子序列）【动态规划】【max_element】

糖逗

题目描述：

1. 给定一个无序的整数数组，找到其中最长上升子序列的长度。
   
2. 
   
3. 示例:
   
4. 
   
5. 输入: [10,9,2,5,3,7,101,18]
   
6. 输出: 4
   
7. 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
   
8. 说明:
   
9. 
   
10. 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
    
11. 你算法的时间复杂度应该为 O(n2) 。
    
12. 
    
13. 来源：力扣（LeetCode）
    
14. 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
    
15. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <vector>
   
4. 
   
5. using namespace std;
   
6. 
   
7. 
   
8. int lengthOfLIS(vector<int>& nums) {
   
9.     int len = nums.size();
   
10.     if(len == 0) return 0;
    
11.     vector<int> dp(len, 0);
    
12.     for(int i = 0; i < len; i++){
    
13.         dp[i] = 1;
    
14.         for(int j = 0; j < i ; j++){
    
15.             if(nums[j] < nums[i]){
    
16.                 dp[i] = max(dp[i], dp[j] + 1);
    
17.             }
    
18.         }
    
19.     }
    
20.     return *max_element(dp.begin(), dp.end());
    
21. 
    
22. }
    
23. 
    
24. int main(void){
    
25.         vector<int> input;
    
26.         int number;
    
27.         while(cin >> number){
    
28.                 input.push_back(number);
    
29.         }
    
30.         cout << lengthOfLIS(input) << endl;
    
31. 
    
32.        
    
33.        
    
34.         return 0;
    
35. }

复制代码

注意事项：
1.参考链接：max_element  https://blog.csdn.net/qq_41970098/article/details/87884651