最长增长子序列(LIS)

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解法1:动态规划 算法复杂度 O(n^2)

1.建立表 length[n]
2.遍历到nums[i]时,建立循环j in 0-(i-1) 如果nums[j]比nums[i]小,length[i]=max(length[i], length[j]+1) 
3.更新maxLength
注:这里额外设置了一个maxlength,是因为nums[i]可能没有起作用
length[i]不表示截止nums[i]的最长增长子序列长度

class Solution {
public:
    int FindMax(int a, int b){
        return a>b ? a:b;
    }
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        ) ;
        int length[n];
        ;
        length[] = ;
        ;i<n;i++){
            length[i] = ;
            ;j<i;j++){
                if(nums[i] > nums[j]){
                    length[i] = FindMax(length[i], length[j]+);
                }
            }
            max = FindMax(max, length[i]);
        }
        return max;
    }
};

解法2:算法复杂度 O(nlogn)

1. 新建立一个数组new[]存放值
2. 遍历原数组nums[]
3. 将nums[i]放入new[]中:找到第一个大于nums[i]的值并替换,如果不存在就直接放到new[]末尾
4. 最后的长度即为这个数组new的长度,但是!!这个数组的内容并不是真实最长增长子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        ; i < nums.size(); ++i) {
            , right = dp.size();
            while (left < right) {
                ;
                ;
                else right = mid;
            }
            if (right >= dp.size()) dp.push_back(nums[i]);
            else dp[right] = nums[i];
        }
        return dp.size();
    }
};
上一篇:PHP 开发 APP 接口 学习笔记与总结 - APP 接口实例 [7] APP 错误日志接口


下一篇:一个基于JRTPLIB的轻量级RTSP客户端(myRTSPClient)——实现篇:(八)RTP音视频传输解析层之MPA传输格式