单调减子序列（java实现）

Keagan 发布于2019-08-15 15:55 / 1485人阅读

摘要：给定整数序列的长度和整数序列中依次的值，请你求出这个整数序列中最长的单调减小的子序列的长度以及不同但长度都是最长得单调减小的子序列的数量。输入第行为一个整数，表示输入的整数序列的长度。对于问题，声明以第个元素为结尾的子序列的最长的长度。

题目：从一个由N个整数排列组成的整数序列中，自左向右不连续的选出一组整数，可以组成一个单调减小的子序列（如从{68 69 54 64 68 64 70 67 78 62 98 87}中我们可以选取出{69 68 64 62}这个子序列；当然，这里还有很多其他符合条件的子序列）。给定整数序列的长度和整数序列中依次的值，请你求出这个整数序列中“最长的单调减小的子序列的长度”以及“不同但长度都是最长得单调减小的子序列的数量”。

   输入第1行为一个整数N，表示输入的整数序列的长度（1≤N≤50000）。输入第2行包括由空格分隔的N个整数（每个整数都在32位长整型范围内）。

输出包括一行，为两个数字，分别为针对给定的整数序列求出的“最长的单调减小的子序列的长度”以及“值不同但长度都是最长得单调减小的子序列的数量”
样例输入
12
68 69 54 64 68 64 70 67 78 62 98 87
样例输出
4 2

对于这个题，一共有两个小部分的问题要解决。前一个问题是最长不上升子序列，属于LIS问题，使用动态规划解决，后一个问题属于去重问题。
对于LIS问题，声明dp[i] 以第i个元素为结尾的子序列的最长的长度。
对第i个元素，与前i-1个元素进行比较：
dp[i] = 1; //当末尾只要一个元素时长度为1
如果 arr[i] < arr[j]:

如果dp[i] < dp[j] + 1
此时dp[i]的值会被更新为dp[j] + 1

其他情况不做处理

对于去重问题：
“值不同但长度都是最长得单调减小的子序列的数量” 这里说的是：

比如输入：
6
2 1 2 1 2 1
输出应为 2 1

2 1 2 1 这两个是值相同的，所以应该当做一个
使用size[i] 数组去记录第i元素为结尾时，值不同但长度都是最长得单调减小的子序列的数量
每次在dp更新一遍以后，进行size的更新。
去掉相同值的情况，如果只去关注最后结尾时：
因为每次遍历都会更新状态，也就是说如果有相同值的时候后者会把前者的情况都会过一遍，所以只要每次更新时保证只取相同值的最后一个出现的元素位置的size[j]即可，也就是最右边的那个。
对于i元素所构成的最长子序列的前一个元素可能有很多不同值，所以要记录这些值,并只取最右边的。
最后size 和 dp都已经生成了最终数组
然后对整个数组进行遍历，找出最大序列且值不同的序列的数量
方法同找单个i位置元素的值不同但长度都是最长得单调减小的子序列的数量一致
其他说明：
数据较大使用java中的BigInteger
遍历找值不同但长度都是最长得单调减小的子序列的数量时使用倒序查找

代码：

Scanner read = new Scanner(System.in);
        int n = read.nextInt();
        long[] arr = new long[n];
        long[] dp = new long[n];
        BigInteger[] size = new BigInteger[n];
        for(int i = 0; i < n; ++i){
            arr[i] = read.nextLong();
        }
        long max = 0;
        
        for(int i = 0; i < n; ++i){
            dp[i] = 1;
            size[i] = new BigInteger("0");
            for(int j = 0; j < i; ++j){
                if(arr[j] > arr[i]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                    }
                }
            }
            if(dp[i] > max){
                //更新 最长长度
                max = dp[i];
            }
            // 确定以arr[i]结尾的 子序列中 值不同但长度都是最长得单调减小的子序列的数量
            if(dp[i] > 1){//如果  不是只有一个数字的时候
                Set sl = new HashSet<>();
                for(int j = i - 1; j >= 0; --j){
                    //从右向左查询  只查询第一次遇到的并且是最大长度的 size[i]
                    // 没有记录路径 通过 arr[j] > arr[i] && dp[j] == dp[i] - 1 来确定是否是前一个转移
                    // 遇到相同结尾的情况，更右边的已经包含了左边的情况
                    if(arr[j] > arr[i] && dp[j] == dp[i] - 1 && !sl.contains(arr[j])){
                        sl.add(arr[j]);//去重
                        size[i] = size[i].add(size[j]);
                    }
                }
            }else{
                //只有一个数字是 数量为1
                size[i] = new BigInteger("1");
            }
        }
        BigInteger maxBigI = new BigInteger("0");
        Set set = new HashSet<>();
        //遍历整个序列  找出最大长度 且值不同的序列的数量
        for(int i = n - 1; i >= 0; --i){
            if(dp[i] == max && !set.contains(arr[i])){
                set.add(arr[i]);
                maxBigI = maxBigI.add(size[i]);
            }
        }
        System.out.println(max + " " + maxBigI.toString());
    }

GPU云服务器云服务器最大子序列最长递增子序列最长公共子序列单序列号

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69324.html

Java String、StringBuffer和StringBuilder类

摘要：可以调用方法将其转换为一个对象是线程安全的，则没有实现线程安全功能，所以性能略高。通过串联更方便将该对象与的对象进行比较。追加字符串插入替换删除反转输出输出改变的长度，将只保留前面部分 String类是不可变类，即一旦一个String对象被创建以后，包括在这个对象中的字符序列是不可改变的，直至这个对象被销毁 StringBuffer对象则代表一个字符序列可变的字符串，当一个String...

Jason 2019-08-14 16:58 评论0 收藏0
Java与Python详细对比

摘要：序列化的这种过程，我们将其称为腌制。而把模块编译成二进制语言程序的这个过程叫做字节编译，这个过程会产生一个与编译的模块对应的文件。常量：在Python中常量的使用并不像java等其他编程语言一样有特定的常量实现的关键字，在Python中定义需要用对象的方法来创建。 showImg(https://segmentfault.com/img/bVP6mZ?w=1232&h=703); ...

tianhang 2019-07-25 12:03 评论0 收藏0
Java与Python详细对比

摘要：序列化的这种过程，我们将其称为腌制。而把模块编译成二进制语言程序的这个过程叫做字节编译，这个过程会产生一个与编译的模块对应的文件。常量：在Python中常量的使用并不像java等其他编程语言一样有特定的常量实现的关键字，在Python中定义需要用对象的方法来创建。 showImg(https://segmentfault.com/img/bVP6mZ?w=1232&h=703); ...

sydMobile 2019-08-16 12:07 评论0 收藏0
Java知识点总结（常用类-字符类）

摘要：知识点总结常用类字符类知识点总结常用类类型用来比奥斯在编码中的字符。使用给定中的字符替换此序列的子字符串中的字符。将此字符序列用其反转形式取代。返回最右边出现的指定子字符串在此字符串中的索引。 Java知识点总结（常用类-字符类） @(Java知识点总结)[Java, Java常用类] [toc] Char char类型用来比奥斯在Unicode编码中的字符。Unicode用来处理各...

xiaokai 2019-08-15 15:34 评论0 收藏0
账户变动合并提交方案

摘要：起因及介绍在早期的账户系统中，但凡有账户变动，就会执行一次数据库操作。这时，在一次处理过程中，合并同一个账户的所有操作，最后只提交一次，就能带来很大的优化空间。根据业务需要，进行增减转账冻结解冻操作。起因及介绍在早期的账户系统中，但凡有账户变动，就会执行一次数据库操作。这样在有复杂一些业务操作的时候，例如单笔交易涉及多个用户多个费用的资金划拨，一个事务内操作数据库几十次也就大量的存...

MoAir 2019-08-19 11:15 评论0 收藏0