当前位置：网站首页>76 · 最长上升子序列

76 · 最长上升子序列

2022-04-22 06:16:00 【yinhua405】

描述

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。

 

最长上升子序列的定义：

最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。
https://en.wikipedia.org/wiki/Longest_increasing_subsequence

样例

样例 1：

输入：

 
 
nums = [5,4,1,2,3]
 
 
输出：
 
 
 
 
3
 
 
解释：
 
 
LIS 是 [1,2,3]
样例 2：
 
 
输入：
 
 
 
 
nums = [4,2,4,5,3,7]
 
 
输出：
 
 
 
 
4
 
 
解释：
 
 
LIS 是 [2,4,5,7]
 
 
挑战
 
 
要求时间复杂度为O(n2)O(n^2)O(n2) 或者 O(nlogn)O(nlogn)O(nlogn)
 
 
 
 

 int longestIncreasingSubsequence(vector<int> &nums) {
  
     // write your code here
     int size = nums.size();
     if (size <= 1)
     {
  
         return size;
     }
     vector<int> dp(size, 1);
     int max = 1;
     //dp[0] = 1;
     for (int i = 1; i<size; i++)
     {
  
         for (int j = i - 1; j >= 0; j--)
         {
  
             if (nums[i] == nums[j])
             {
  
                 dp[i] = dp[i]>dp[j] ? dp[i] : dp[j];
             }
             else if (nums[i] > nums[j])
             {
  
                 dp[i] = dp[i]>dp[j] + 1 ? dp[i] : dp[j] + 1;
                 if (dp[i] > max)
                 {
  
                     max = dp[i];
                 }
             }
         }
     }
 
 

     return max;
 }
 
 
 


                

                    
版权声明 

                        本文为[yinhua405]所创，转载请带上原文链接，感谢

                        https://blog.csdn.net/yinhua405/article/details/122613685
                    

                

            


            
            



            


        

        

        

    

    

        



        


边栏推荐





        


猜你喜欢

        



        


随机推荐