算法练习：数组最长递增子序列问题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法练习：数组最长递增子序列问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1770字，纯文字阅读大概需要3分钟。

内容图文

• 基础算法原型问题：《程序员代码面试指南》page 202
  
  主要解题思路：求解dp[i]，表示以arr[i]这个数结尾的情况下， 最长递增子序列的长度.
• O（N*N）的做法：源码
  
• O（N* logN）的解法， 求解dp[i]，源码

    /***
     * 1. 增加辅助数组 ends[b]和right 变量。
     * 2. ends[b] 表示 长度为b+1 的递增子序列的最小结尾数是ends[b]; ends[0....right].ends 一定为
     * 一个递增数组
     * 为有效去，ends[right+1,....N-1]为无效区。
     * 3. 遍历（ends 为递增，可以使用二分查找）：
     *     3.1 在遍历arr[i]的过程中，查找ends[0,...right-1],存在比arr[i]大的则可以用arr[i]替换掉。
     *     3.2 如果ends 中 都比 arr[i] 小，则有效区间 右移
     */
     public int[] getdp2(int[] arr){
        int[] dp = new int[arr.length];
        int[] ends = new int[arr.length];
        ends[0] = arr[0];
        int right = 0;
        int l =0;
        int r =0;
        int m=0;
        // 二分查找 比arr[i] 大的数,ends 为递增数组。
        for(int i=1; i < arr.length; i++){
            l=0;
            r=right;
            while(l <= r){
                m=(l+r)/2;
                if(arr[i] > ends[m]){
                    l= m+1;
                }else{
                    //找到第一个大于arr[i]的值
                    r= m-1;
                }
            }
            right = Math.max(right,l);
            ends[l] = arr[i];
            dp[i] = l+1;
        }
        return dp;
    }

详细解题思路 参考《程序员代码面试指南》page 202

3. 给定一个N2的二维数组，看作是一个个二元组，例如[[a1,b1],[a2,b2],[a3,b3]]，规定：一个如果想把二元组甲放在二元组乙上，甲中的a值必须大于乙中的a值，甲中的b值必须大于乙中的b值。如果在二维数组中随意选择二元组，请问二元组最多可以往上摞几个？例如：[[5,4],[6,4],[6,7],[2,3]],最大数量可以摞3个，[2,3]=>[5,4]=>[6,7]要求：实现时间复杂度O(NlogN)的解法 （俄罗斯沙皇问题， leetcode 354）

   解题思路：算法原型如2中的求解最长递增子序列，先按a从小到大进行排序，当a相同时，按b从大到小排序。然后求解b的最长递增子序列。为什么这个算法可行： 排序之后的数据在， 后面出现的二元组的a 肯定大于前面出现的二元组的a, 同时 求b 的最长递增子序列，也能保证 这个序列中的b 是递增的。通过上面的排序算法， 将 这个问题 还原到 2 中的问题求解。
   算法讲解
   算法实现

参考

左程云 《程序员代码面试指南》

内容总结

以上是互联网集市为您收集整理的算法练习：数组最长递增子序列问题全部内容，希望文章能够帮你解决算法练习：数组最长递增子序列问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---