精华内容
下载资源
问答
  • 1713. 得到子序列的最少操作次数 给你一个数组target,包含若干 互不相同的整数,以及另一个整数数组arr,arr可能 包含重复元素。 每一次操作中,你可以在 arr的任意位置插入任一整数。比方说,如果arr = [1,4,1,...

    1713. 得到子序列的最少操作次数

    给你一个数组 target ,包含若干 互不相同 的整数,以及另一个整数数组 arr ,arr 可能 包含重复元素。

    每一次操作中,你可以在 arr 的任意位置插入任一整数。比方说,如果 arr = [1,4,1,2] ,那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。

    请你返回 最少 操作次数,使得 target 成为 arr 的一个子序列。

    一个数组的 子序列 指的是删除原数组的某些元素(可能一个元素都不删除),同时不改变其余元素的相对顺序得到的数组。比方说,[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列(加粗元素),但 [2,4,2] 不是子序列。

    示例 1:

    输入:target = [5,1,3], arr = [9,4,2,3,4]
    输出:2
    解释:你可以添加 5 和 1 ,使得 arr 变为 [5,9,4,1,2,3,4] ,target 为 arr 的子序列。
    示例 2:

    输入:target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
    输出:3

    提示:

    1 <= target.length, arr.length <= 105
    1 <= target[i], arr[i] <= 109
    target 不包含任何重复元素。
    通过次数1,445提交次数3,140

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence

    解析:

    ans=len(A)-LCS(A,B),LCS:最长公共子序列

    方法一:DP法

    • 定义:dp[i][j] = A[:i] 和B[:j]的LCS
    • 初始化:dp[*][*] = 0
    • 公式:dp[i][j] = max(dp[i-1][j], dp[i][j-1],dp[i-1][j-1]+A[i]==B[j])
    • 结果:dp[m][n]
    • 复杂度:O(mn)
    • 通过情况:63 / 82 个通过测试用例
    def minOperations1(target, arr):
        m, n = len(target), len(arr)
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                dp[i][j] = max([dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + int(target[i-1] == arr[j-1])])
        return len(target) - dp[m][n]

    方法二(优化):

    注意题中的提示:target 不包含任何重复元素。

    target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]

    将target 转换成序号:[0,1,2,3,4,5]

    arr相应数字也进行替换:[1,0,5,4,2,0,3],没有的删除

    由于target序号一定是递增序列,因此本题可以转换成寻找-最长单调递增子序列,参见:300. 最长递增子序列

    复杂度:O(n)

    def minOperations2(target, arr):
        def LIS(A) -> int:
            dp = []
            for x in A:
                if not dp or x > dp[-1]:
                    dp.append(x)
                else:
                    dp[bisect_left(dp, x)] = x
            return len(dp)
    
        map_set = {x: i for i, x in enumerate(target)}
        new_arr = [map_set.get(x) for x in arr if x in map_set]
        return len(target) - LIS(new_arr)

     

    展开全文
  • 问题给定一个未排序的整数数组,给出这个数组的最长递增子序列长度。举例如下:输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长递增子序列是 [2,3,7,101], 所以长度为 4. 问题来源: ...

    问题

    给定一个未排序的整数数组,给出这个数组的最长递增子序列长度。举例如下:

    输入: [10,9,2,5,3,7,101,18]
    输出: 4
    解释: 最长递增子序列是 [2,3,7,101], 所以长度为 4.

    问题来源: https://leetcode.com/problems/longest-increasing-subsequence/

    解答一

    首先我们试着应用动态规划的思想去解决这个问题。假设为排序的数组为A, 动态规划记录表为数组dp, dp[i]表示以A[i]结尾的最长递增子序列长度, 如A=[10,9,2,5,3,7,101,18], 有dp=[1,1,1,2,2,3,4,4]。问题转化为根据dp[0...i-1]求解dp[i]。思路见如下代码片段:

    for(int i=0; i<A.length; i++){
      dp[i] = 1;     // initialize 
      for(int j=i-1; j>=0; j--){
        if(A[j]<A[i]){
          dp[i] = Math.max(dp[i], dp[j]+1);
        }
      }
    }

    容易看出,时间复杂度为

    解答二

    我们通过改变记录表中元素的意义进一步优化效率。 假设我们记录表的名字叫tails, tails的索引i并不表示A中第i个元素索引,而是用来表示当前递增子序列的长度i+1。tails[i]表示当前递增子序列长度为i+1时,子序列结尾数的最小值(因为有多个长度为i+1的递增子序列)。遍历数组A时,对于某个元素e,找到e在tails中的位置,假设tails目前长度为size,

    1. 如果找到某个j,使得tails[j-1]<e<=tails[j], 更新tails[j] = e;
    2. 否则e>tails[tails.size], 那么tails[size+1] = e,size也自然增加1;

    显然tails是有序的,可以使用二分查找e在tails的中位置。代码如下。该算法时间复杂度为O(nlogn)

          public int lengthOfLIS(int[] nums) {
            int[] tails = new int[nums.length];
            int size = -1;
            if(nums.length > 0) {
                tails[++size] = nums[0];
            }
            for(int i=1; i<nums.length; i++) {
                int j = binarySearch(tails, 0, size, nums[i]);
                if(j<=size){
                    tails[j] = nums[i];
                }else{
                    tails[++size] = nums[i];
                }
            }
            return size+1;
        }
        
        /**
        二分搜索,返回arr中第一个不小于val的元素索引
        */
        int binarySearch(int[] arr, int begin, int end, int val){
            while(begin < end){
                int mid = (begin+end)/2;
                if(arr[mid] < val) {
                    begin = mid+1;
                }else{
                    end = mid;
                }
            }
            return arr[begin]>=val?begin:(begin+1);
        }
    展开全文
  • 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有多种最长上升子序列的组合,你只...

    题目一

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

    示例:

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

    说明:

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

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


    方法一:动态规划


    解题思路

    1. 思考定义状态:每个元素都可能作为最后最长递增子序列的末尾。

    2. 定义dp[i]dp[i]为以数组中第i个元素为结尾的最长递增子序列的长度。

    3. 初始化:由于每个元素单独都可以作为一个递增子序列,因此 dpdp 数组全部初始化为1。

    4. 状态转移:dp[i]=nums[i]+max(dp[i1],dp[i2],...)dp[i] = nums[i] + max(dp[i - 1], dp[i - 2], ...)。注:maxmax 中的原数组元素必须严格小于nums[i]nums[i],这样nums[i]nums[i]才能够接在他们后面构成最长递增子序列。

    5. 最终结果:就是遍历 dpdp 数组找到其中的最大值。

    代码一

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            if(nums.size() < 2){
                return nums.size();
            }
    
            //每次的一个新数,都把他当作结尾,找以他结尾的最长字串,他需要对前面的所有dp进行遍历
            vector<int> dp(nums.size(), 1);
            int maxLen = 1;
            for(int i = 1; i < nums.size(); ++i){
                for(int j = 0; j < i; ++j){
                    if(nums[j] < nums[i]){
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
                maxLen = max(maxLen, dp[i]);
            }
            return maxLen;
    
        }
    };
    

    时间复杂度:O(n2)O(n^2)
    空间复杂度:O(n)O(n)


    方法二:动态规划,二分查找


    解题思路

    1. 重新定义状态:tail[i]tail[i]代表长度为 i+1i+1 的递增子序列的最小值
    2. 每次加入一个元素:若该元素大于维护的数组中的元素,则将该元素放入数组。否则,查找该元素可以作为的递增子序列的最小值,替换元素。
    3. 在查找替换位置的时候,因为 tailtail 中的元素是递增的,所以可以采用二分查找来插入元素。

    代码二

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            if(nums.size() < 2){
                return nums.size();
            }
    
            /*
            方法二:重新定义状态:dp[i]代表长度为i+1的递增子序列的最小值
            每次加入一个元素:若该元素大于维护的数组中的元素,则将该元素放入数组
            否则,查找该元素可以作为的递增子序列的最小值,插入
            */
    
            vector<int> tail;
            int end = 0;    //标识序列结尾
            tail.push_back(nums[0]);
    
            for(int i = 1; i < nums.size(); ++i){
                if(nums[i] > tail[end]){
                    tail.push_back(nums[i]);
                    end++;
                }
                else{
                    //查找该元素可以作为的递增子序列最小值的插入位置
                    //即就是查找【0,end】中第一个大于等于tail[end]的位置
                    int left = 0;
                    int right = end;
                    while(left < right){
                        int mid = left + (right - left) / 2;
                        if(tail[mid] >= nums[i]){
                            right = mid;
                        }
                        else{
                            left = mid + 1;
                        }
                    }
                    tail[left] = nums[i];
                }
            }
    
            return end + 1;
        }
    };
    

    时间复杂度:O(nlogn)O(nlogn)
    空间复杂度:O(n)O(n)


    题目二

    有个马戏团正在设计叠罗汉的表演节目,一个人要站在另一人的肩膀上。出于实际和美观的考虑,在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重,请编写代码计算叠罗汉最多能叠几个人。

    示例:

    输入:height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
    输出:6
    解释:从上往下数,叠罗汉最多能叠 6 层:(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)

    提示:

    • height.length == weight.length <= 10000

    解题思路

    1. 题目给出两个维度,两个维度上都满足严格递增的要求才可以叠上去。
    2. 考虑需要严格递增,先按照 heightheight 升序排序,同时 heightheight 相同的人按照 weightweight 降序排序。
    3. 这样排序下来,直接在数组中查找关于 weightweight 的最长递增子序列就能得到答案。
    4. 一个升序,一个降序的是与我们的解决方法相关(我们在排序之后,直接查找体重的最长递增子序列就能得到答案),如: height=[3,2,2,3,1,6]weight=[7,3,5,6,2,10]height = [3, 2, 2, 3, 1, 6],weight = [7,3,5,6,2,10]。两个都升序的排序结果是 height=[1,2,2,3,3,6]weight=[2,3,5,6,7,10]height = [1, 2, 2, 3, 3, 6],weight = [2,3,5,6,7,10],直接查找体重的最长递增子序列结果是 66,可以看到,同一身高内部可能存在体重的递增。因此,会被加入结果。而使用身高升序,体重降序,排序结果为height=[1,2,2,3,3,6]weight=[2,5,3,7,6,10]height = [1, 2, 2, 3, 3, 6],weight = [2,5,3,7,6,10],可以看到体重的最长递增子序列结果是 44

    代码

    class Solution {
    public:
        int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
            //构造最长递增序列,用身高升序排序,同时体重降序排序,然后在体重中查找最长递增子序列
            vector<Person> persons;
            for(int i = 0; i < height.size(); ++i){
                persons.push_back(Person(height[i], weight[i]));
            }
    
            sort(persons.begin(), persons.end());
            //然后用一个数组dp[i]表示长度为i+1长度的递增子序列的结尾最小值
            vector<int> dp;
            dp.push_back(persons[0].weight);
            int end = 0;
    
            for(int i = 1; i < persons.size(); ++i){
                if(persons[i].weight > dp[end]){
                    dp.push_back(persons[i].weight);
                    ++end;
                }
                else{
                    //查找第一个大于等于persons[i].weight的位置
                    int left = 0;
                    int right = end;
                    while(left < right){
                        int mid = left + (right - left) / 2;
                        if(dp[mid] >= persons[i].weight){
                            right = mid;
                        }
                        else{
                            left = mid + 1;
                        }
                    }
                    dp[left] = persons[i].weight;
                }
            }
            return end + 1;
        }
    private:
        struct Person{
            int height;
            int weight;
            Person(int _height, int _weight): height(_height), weight(_weight){}
            bool operator < (const Person &person) const{
                if(height != person.height){
                    return height < person.height;
                }
                else{
                    return weight > person.weight;
                }
            }
        };
    
    };
    

    时间复杂度:O(nlogn)O(nlogn)
    空间复杂度:O(n)O(n)


    题目三

    堆箱子。给你一堆n个箱子,箱子宽 wi、深 di、高 hi。箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法,搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。输入使用数组[wi, di, hi]表示每个箱子。

    示例1:

    输入:box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
    输出:6

    示例2:

    输入:box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
    输出:10

    提示:

    • 箱子的数目不大于3000个。

    解题思路

    1. 与马戏团叠罗汉相同的思路,只不过这里的约束变成了三维,只有三个方向都满足严格递增,才能选择此时的箱子。实际就是找第一维固定情况下的最长递增子序列,只不过这个子序列需要满足两个条件的约束。
    2. dp[i]dp[i] 表示以i结尾的最长递增子序列的高度最大值。
    3. 状态转移:dp[i]=max(dp[i],dp[j]+box[i][2])dp[i] = max(dp[i], dp[j] + box[i][2]),其中 jj 取小于等于 ii 的全部值。
    4. 最终结果为 dpdp 数组中的最大值。

    代码

    class Solution {
    public:
        int pileBox(vector<vector<int>>& box) {
            if(box.size() < 2){
                return box.size();
            }
            //实际就是找第一维固定情况下的最长递增子序列,只不过这个子序列需要满足两个条件的约束
            //用dp[i]表示以i结尾的最长递增子序列的高度最大值
            sort(box.begin(), box.end(), cmp);
    
            int n = box.size();
            vector<int> dp(n, 0);
            dp[0] = box[0][2];
            int maxHeight = dp[0];
    
            for(int i = 1; i < n; ++i){
                //向前寻找满足条件的
                dp[i] = box[i][2];
                for(int j = 0; j < i; ++j){
                    if(box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2]){
                        dp[i] = max(dp[i], dp[j] + box[i][2]);
                    }
                }
                maxHeight = max(maxHeight, dp[i]);
            }
    
            return maxHeight;
        }
    private:
        static bool cmp(vector<int> &a, vector<int> &b){    //较短较窄较低的箱子排在前面方便选择
            return a[2] < b[2];	//没必要写好几个排序:只需要按照一个维度排序就行,因为在计算每一个元素作为序列末尾元素时都需要满足三个维度上严格递增
        }
    };
    

    时间复杂度:O(n2)O(n^{2})
    空间复杂度:O(n)O(n)


    展开全文
  • 问题描述:  从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大... 假设一个数组arr[n],它的分段点是i(0-i递增,i到n-1递减),假设我们用方法LIS(i)(最长递增子序列)找到从0到i的递增子序列,LDS找到

    注:转自博客http://blog.chinaunix.net/uid-26548237-id-3757779.html

    问题描述:

        从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的。

    解题思路:
        假设一个数组arr[n],它的分段点是i(0-i递增,i到n-1递减),假设我们用方法LIS(i)(最长递增子序列)找到从0到i的递增子序列,LDS找到从i到n-1的最长递减子序列,那么它的总长度为LIS(i) + LDS(i) - 1,所以我们扫描整个数组,即让i从0到n-1,找出使LIS(i) + LDS(i) - 1最大的即可。

        下面先讲解最长递增子序列的求解方法。
    (1)动态规划
        以i结尾的序列的最长递增子序列和其[0, i - 1]“前缀”的最长递增子序列有关,设LIS[i]保存以i结尾的最长递增子序列的长度:
        若i = 0,则LIS[i] = 1;
        若i > 0,则LIS[i]的值和其[0, i - 1]前缀的最长递增子序列长度有关,用j遍历[0, i - 1]得到其最长递增子序列为LIS[j],对每一个LIS[j],如果序列array[j]  < array[i]并且LIS[j] + 1 > LIS[i],则LIS[i]的值变成LIS[j] + 1。即:
        LIS[i] = max{1, LIS[j] + 1},其中array[i] > array[j] 且 j = [0, i - 1]。
        代码如下所示。
    1. int MAX(int *LIS,int len)
    2. {
    3.     int max = 0;
    4.     for(int i = 0;< len;++i)
    5.     {
    6.         cout<<i<<" "<<LIS[i]<<endl;
    7.         if(LIS[i] > max)
    8.             max = LIS[i];
    9.     }
    10.     return max;
    11. }

    12. int LIS(int *array,int len)
    13. {
    14.     int *LIS = new int[len];//用于记录当前各元素作为最大元素的最长递增序列长度
    15.     for(int i = 0;< len;++i)
    16.     {
    17.         LIS[i] = 1;//设置当前元素array[i]作为最大元素的最长递增序列长度为1
    18.         for(int j = 0; j < i;++j)
    19.         {
    20.             if(array[i] > array[j] && LIS[j] + 1 > LIS[i])
    21.             {
    22.                 LIS[i] = LIS[j] + 1;
    23.             }
    24.         }
    25.     }
    26.     int res = MAX(LIS,len);
    27.     delete LIS;
    28.     return res;//获得LIS中的最大值并返回;
    29. }
    (2)二分查找+动态规划实现
        假设存在一个序列d[1...9] = 2 1 5 3 6 4 8 9 7,可以看出它的LIS长度是5。
        下面一步一步试着找到它。
        我们定义一个序列B,然后令i = 1 to 9逐个考察这个序列。
        此外,我们用一个变量len来记录现在的最长算到多少。
        首先,把d[1]有序的放到B中,令B[1] = 2,就是说当只有一个数字2的时候,长度为1的LIS的最小末尾是2,这时len = 1;
        然后,把d[2]有序的放到B中,令B[1] = 1,就是说长度为1的LIS的最小末尾是1,d[1] = 2已经没用了,很容易理解吧,这时len = 1;
        接着,d[3] = 5,d[3] > B[1],所以令B[1 + 1] = B[2] = d[3] = 5,就是说长度为2的LIS的最小末尾是5,很容易理解吧,这时B[1...2] = 1, 5,len = 2;
        再来,d[4] = 3,它正好在1,5之间,放在1的位置显然不合适,因为1小于3,长度为1的LIS最小末尾应该是1,这样很容易推知,长度为2的LIS最小末尾是3,于是可以把5淘汰掉,这时B[1...2] = 1,3,len = 2;
        继续,d[5] = 6,它在3的后面,因为B[2] = 3,而6在3后面,于是很容易推知B[3] = 6,这时B[1...3] = 1,3,6,还是很容易理解吧?这时len = 3;
        第6个,d[6] = 4,你看它在3和6之间,于是就可以把6替换掉,得到B[3] = 4。B[1...3] = 1,3,4,这时len = 3;
        第7个,d[7] = 8,它很大,比4大,于是B[4] = 8,这时len = 4;
        第8个,d[8] = 9,得到B[5] = 9,len继续增大,这时len = 5;
        最后一个,d[9] = 7,它在B[3] = 4和B[4] = 8之间,所以我们知道,最新的B[4] = 7, B[1...5] = 1,3,4,7,9,len = 5。
        于是我们知道了LIS的长度为5。
        注意,注意。这个1,3,4,7,9不是LIS,它只是存储了对应长度LIS的最小末尾。有了这个末尾,我们就可以一个一个地插入数据。虽然最后一个d[9] = 7更新进去对于这个数组数据没有什么意义,但是如果后面再出现两个数字8和9,那么就可以把8更新到d[5],9更新到d[6],得到LIS的长度为6。
        然后应该发现一件事情了:在B中插入数据是有序的,而且进行替换而不需要移动——也就是说,可以使用二分查找,将每一个数字的插入时间优化到O(logn),于是算法的时间复杂度就降低到了O(nlogn)了。
        代码如下:
    1. int LIS(int *array,int len)
    2. {
    3.     //LIS数组中存储的是 递增子序列中最大值最小的子序列的最后一个元素(最大元素)在array中的位置
    4.     int *LIS = new int[len];
    5.     int left,mid,right;
    6.     int max=1;
    7.     LIS[0]=array[0];
    8.     for(int i = 1;< len;++i)
    9.     {
    10.         left = 0;
    11.         right = max;
    12.         while(left <=right)
    13.         {
    14.             mid = (left+right)/2;
    15.             if(LIS[mid] < array[i])
    16.                 left = mid +1;
    17.             else
    18.                 right = mid -1;
    19.         }
    20.         LIS[left] = array[i];//插入
    21.         if(left > max)
    22.         {
    23.             max++;
    24.         }
    25.     }
    26.     delete LIS;
    27.     return max;
    28. }
        
        下面就开始实现“从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的“这个问题。
        双端LIS问题,用动态规划的思想可以解决,目标规划函数为max{B[i] + C[i] - 1},其中B[i]是从左到右的,0~i个数之间满足递增的数字个数;C[i]为从右到左的,n- 1 ~ i个数之间满足递增的数字个数。最后结果为n - max + 1,其中动态规划的时候,可以用二分查找进行处理,如上述求最长递增子序列的方法二。
        代码如下。
    1. /*
    2. *copyright@nciaebupt 转载请注明出处
    3. *问题:从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的(网易)。
    4. *比如数列1,4,3,5,6,7,2,0 删除的最少的数的个数为1
    5. *求解思路:双端LIS问题,使用动态规划的思路求解,时间复杂度O(nlog(n))
    6. */
    7. #include <cstdio>
    8. #include <iostream>

    9. using namespace std;

    10. int DoubleEndLIS(int *array,int len)
    11. {
    12.     int left,mid,right;
    13.     int max=0;
    14.     int k =0;

    15.     //LIS数组中存储的是 递增子序列中最大值最小的子序列的最后一个元素(最大元素)在array中的位置
    16.     int *LIS = new int[len];
    17.     //从左到右LIS中最长子序列中最大值最小的子序列的最后一个元素所在的位置,也就是0~i的数字序列中最长递增子序列的长度-1
    18.     int *= new int[len];
    19.     //从右到左LIS中最长子序列中最大值最小的子序列的最后一个元素所在的位置,也就是len-1~i的数字序列中最长递增子序列的长度-1
    20.     int *= new int[len];
    21.     //从左到右
    22.     for(int i = 0;< len;++i)//LIS数组清零
    23.     {
    24.         B[i] = 0;
    25.         LIS[i] = 0;
    26.     }
    27.     LIS[0] = array[0];
    28.     for(int i = 1;< len;++i)
    29.     {
    30.         left = 0;
    31.         right = B[k];
    32.         while(left <= right)
    33.         {
    34.             mid = (left + right)/2;
    35.             if(array[i] < LIS[mid])
    36.             {
    37.                 right = mid - 1;
    38.             }
    39.             else
    40.             {
    41.                 left = mid + 1;
    42.             }
    43.         }

    44.         LIS[left] = array[i];//将array[i]插入到LIS中
    45.         if(left > B[k])
    46.         {
    47.             B[k+1] = B[k] + 1;
    48.             k++;
    49.         }
    50.     }
    51.     for(int i = 0;< k;++i)
    52.     {
    53.         B[i]++;
    54.     }
    55.     //从右到左
    56.     for(int i = 0;< len;++i)//LIS数组清零
    57.     {
    58.         C[i] = 0;
    59.         LIS[i] = 0;
    60.     }
    61.     k = 0;
    62.     LIS[0] = array[len-1];
    63.     for(int i = len-2;>= 0;--i)
    64.     {
    65.         left = 0;
    66.         right = C[k];
    67.         while(left <= right)
    68.         {
    69.             mid = (left + right)/2;
    70.             if(array[i] < LIS[mid])
    71.             {
    72.                 right = mid - 1;
    73.             }
    74.             else
    75.             {
    76.                 left = mid + 1;
    77.             }
    78.         }
    79.         LIS[left] = array[i];
    80.         if(left > C[k])
    81.         {
    82.             C[k+1] = C[k] + 1;
    83.             k++;
    84.         }
    85.     }
    86.     for(int i = 0;<= k;++i)
    87.     {
    88.         C[i]++;
    89.     }

    90.     //求max
    91.     for(int i = 0;< len;++i)
    92.     {
    93.         //cout<<B[i]<<" "<<C[i]<<endl;
    94.         if(B[i]+C[i]>max)
    95.             max=B[i] + C[i];
    96.     }

    97.     return len - max +1;
    98. }

    99. int main(int args,char ** argv)
    100. {
    101.     int array[] = {1,4,3,5,6,7,2,0};
    102.     int len = sizeof(array)/sizeof(int);
    103.     int res = DoubleEndLIS(array,len);
    104.     cout<<res<<endl;
    105.     getchar();
    106.     return 0;
    107. }
    展开全文
  • 动态规划应用--最长递增子序列 LeetCode 300

    千次阅读 多人点赞 2019-07-26 00:44:07
    比如2,9,3,6,5,1,7这样一组数字序列,它的最长递增子序列就是2,3,5,7,所以最长递增子序列的长度是4。 2. 解题思路 2.1 回溯法求解 /** * @description: 最长递增子序列 * @author: m...
  • 最长递增子序列问题

    2019-08-11 00:10:59
    最长递增子序列问题 合唱队问题应用: 最长公共子串 LCS: : 最长递增子序列问题 问题:给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度为6的数组A...
  • 这是一道解法很骚的题目,是最长递增子序列应用 直接说解法,先进行排序,长度升序,高度降序排序 然后把高度全去下来找最长递增子序列 这么做的正确性: 首先套信封是严格长和高都要小于才能套进去的,不能等于 ...
  • 最长递增子序列问题问题描述:有一个数组长为n,请求出这个序列中最长的递增子序列的长度。( 递增子序列:对于任意的i 都满足ai 的子序列 )样例输入: 5 4 2 3 1 5样例输出: 3分析:按照解决动态规划的前3个...
  • [编程题] 最长递增子序列 对于一个数字序列,请设计一个复杂度为O(nlogn)的算法,返回该序列的最长上升子序列的长度,这里的子序列定义为这样一个序列U1,U2...,其中...// 最长递增子序列.cpp : 定义控制台应用程序
  • 最长递增子序列

    千次阅读 2018-10-06 13:51:30
    动态规划:是求解决策过程的最优方法,是把多阶段过程转为多阶段过程然后逐个求解,...(注:子序列的每一项都属于原数列,且不一定连续)举个例子,假如输入的数列为3 6 1 4 2 8 9 5 7,那么它的最长子序列一共有五...
  • 最长递增子序列在Virtual DOM算法中的意义如果了解过 ivi/inferno 的同学应该知道,在 ivi/inferno 中 Virtual DOM 的核心 Diff 算法中应用到了求解给定序列的最长递增子序列的算法,用的算法来自:...
  • 给定一个未排序的整数数组,找到最长递增子序列的个数。 示例 1: 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 示例 2: 输入: [2,2,2,2,2] 输出: 5 解释: 最长...
  • 动态规划则应用问题重叠的情况,通常用来求解最优化问题。这类问题可以有很多可行解,每个解都有一个值,我们希望寻找最优值的解。 通常有4个步骤来设计动态规划算法: 1.刻画一个最优解的结构特征。 2...
  • // 求最长递增子序列.cpp : 定义控制台应用程序的入口点。 //动态规划思想 #include "stdafx.h" #include #include using namespace std; int dynamicProgram(int *arry,int n) { //list[i]存储着以arry[i]为...
  • 参考链接: a.http://www.programfan.com/blog/article.asp?id=13086 ...   1.对(http://hao3100590.iteye.com/blog/1548135)中问题6:最长递增子序列的改进,减少时间复杂度 算法的思想:  ...
  • 题目分析:长度为 的数列 有多达 个子序列,但我们应用动态规划法仍可以很高效地求出最长递增子序列()。这里介绍两种方法。 先考虑用下列变量设计动态规划的算法。这里设输入数列的第一个数为 。 一位...
  • 题目大意:可以将0替换成任意interger(包括负数),在此基础上求最长递增子序列。 解题思路:无疑LIS,将所有的0全部提取出来,求出此时序列的LIS(不含0的),这是针对0在子序列的外面的情况,如0,1,2,3,0....
  • // 编程之美之最长递增子序列.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include #include using namespace std; #define N 8 #define MAXN 1003 int A[MAXN]; int MaxV[MAXN]; // 动态规划...
  • 最长递增子序列应用。从前往后跑一遍,然后从后往前跑一遍。最后枚举。#include #include template void Get_Max(T& a,T b){ if(a) a=b;}using namespace std;double height[1005],temp_height;double min_height...
  • 1 // zuichangdizengzixulie.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.h" 5 #include <iostream> 6 #include <vector> 7 #include <iterator> 8 using ...
  • 最长单调递增子序列

    2010-03-17 14:46:00
    //最长单调递增子序列//O(n*n)时间的算法,找出由n个数组组成的序列的最长单调递增子序列//b[i]记录以a[i]为结尾元素的最长单调递增子序列的长度 2 3 8 4 9 结果为长度4,即2389或2349/*******#include "stdafx.h...

空空如也

空空如也

1 2 3 4 5 6
收藏数 113
精华内容 45
关键字:

最长递增子序列应用