算法研究:已知不重复的int集合,求最长递增子序列

问题背景:最近换工作面试,面试官问了一道编程题,大体是已知不重复的int集合,求最长递增子集合,这个集合可以不是连续的,但顺序呢不能乱。

比如说:{2, 7, 3, 13, 6, 8}里最长递增子集合的就是{2,3,6,8}。

这道题感觉很有意思,于是回家就用代码实现了一遍。

主要代码:

package com.galaxy.fym.algorithm.maxsublist;

import org.apache.commons.collections.CollectionUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fengyiming on 2017/2/16.
 * @author fengyiming 对int集合转化成所有可能的递增子集合
 */
public class Search {

    public static List<List<Integer>> search(List<Integer> list) {
        List<List<Integer>> allList = new ArrayList<List<Integer>>();
        int size = list.size();
        for (int i = 0; i < size; i++) {
            int value = list.get(i);
            //这个集合用来存储如果当前value被加入到其他子集合的时候保存被加入的子集合的原值
            List<List<Integer>> newAllList = new ArrayList<List<Integer>>(allList.size());
            //对已存在的子集合集合遍历,判断当前元素是否小于子集合,是的话就加在结尾,另外保存当前子集合
            if(CollectionUtils.isNotEmpty(allList)) {
                for (List<Integer> subList : allList) {
                    int subSize = subList.size();
                    int last2Value = subList.get(subSize - 1);
                    if (last2Value < value) {
                        //如果仅次于,便不用添加了
                        if(value - last2Value > 1) {
                            newAllList.add(new ArrayList<Integer>(subList));
                        }
                        subList.add(value);
                    }
                }
            }
            //将被加入元素的子集合的原值放入到所有子集合里
            if(CollectionUtils.isNotEmpty(newAllList)){
                allList.addAll(newAllList);
            }
            //新建一个仅含当前元素的子集合
            List<Integer> newSubList = new ArrayList<Integer>(size - 1);
            newSubList.add(value);
            allList.add(newSubList);
        }
        return allList;
    }

    public static List<List<Integer>> getMaxList(List<List<Integer>> allList){
        System.out.println("---------------所有递增子集合-------------");
        int max = 0;
        List<List<Integer>> allSubList = new ArrayList<List<Integer>>();
        for (List<Integer> subList : allList) {
            for (Integer value : subList) {
                //System.out.print(value + " ");
            }
            if (subList.size() > max) {
                max = subList.size();
                allSubList = new ArrayList<List<Integer>>();
                allSubList.add(subList);
            } else if (subList.size() == max) {
                allSubList.add(subList);
            }
            //System.out.println();
        }
        System.out.println("---------------最长的子集合-------------");
        for (List<Integer> subList : allSubList) {
            for (Integer value : subList) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
        return allList;
    }
}

测试结果(我隐藏了输出所有集合的结果)(mac pro,i7 4核)

---------------随机数列-------------
17 13 16 8 5 25 10 18 14 0 27 3 2 9 7 4 44 29 12 30
---------------随机数列-------------
消耗时间10ms
总集合长度538
去重后集合长度538
重复元素数量0
---------------最长的子序列-------------
13 16 25 27 29 30
13 16 18 27 29 30
8 10 18 27 29 30
5 10 18 27 29 30
8 10 14 27 29 30
5 10 14 27 29 30 

Process finished with exit code 0

总结:花了1个多小时写这段代码,感觉这道题重要的难点就是不连续的子集合这点,因为所有子集合数量应该是集合大小的阶乘。但是递增子集合就会少很多。

时间: 2025-01-19 15:42:49

算法研究:已知不重复的int集合,求最长递增子序列的相关文章

图的算法问题 已知边的起止节点求其中一个系统节点总数

问题描述 图的算法问题 已知边的起止节点求其中一个系统节点总数 求大神帮我想个算法,我有n组数据对,src->target,展示出来就是数个有向无环图,每个分隔的图称为一个系统,要求给出两个数据我能知道这两个数在不在同一个系统以及这个系统的节点总数是多少.有没有什么简单可行的方法啊计算二叉树的节点总数"> 解决方案 无非就是递归遍历.你每个节点除了本身数据之外,加上一个bool值表示是否被遍历过,伪代码如下: int countNode(Node n) { int r = 0; n.

加密解密算法-已知VB编写的加密算法,求破对应解密算法!

问题描述 已知VB编写的加密算法,求破对应解密算法! 求大神编写对应的解密算法!跪谢! Dim Psw As String Dim Key As String Psw = Trim(Text1.Text) Key = StrReverse(Psw) Key = Key & Left(Key, 1) & Right(Key, 1) Key = Key & Key & Key Dim Val As String Dim Idx1 As Integer Dim Idx2 As I

已知一个坐标A(x,y),求离A最近的N个坐标点,这个怎么算?

问题描述 已知一个坐标A(x,y),求离A最近的N个坐标点,这个怎么算? 解决方案 解决方案二:有人知道吗,帮忙解决一下啊解决方案三:一个个算出来比较啊解决方案四:8个啊x-1,y-1x-1,yx-1,y+1x,y-1x,y+1x+1,y-1x+1,yx+1,y+1解决方案五:如何算,如何比较,一共有几十万个坐标点,不可能一个一个的算和比较吧解决方案六://两点坐标距离为(X-X1)平方+(Y-Y1)平方再开根号intx;inty;intiTemp=...;sPoints[0]与坐标X,Y的距离

已知大概的明文和密文求加密方式(应该是base64变种)

问题描述 已知大概的明文和密文求加密方式(应该是base64变种) 18162417601 YD038bCdLp0Og8ocviQn 18162417602 YD038bCdLp0Og8ocvSQn 18162417603 YD038bCdLp0Og8ocvyQn 18162417609 YD038bCdLp0Og8octSQn 前面一列是明文,后面的是加密后的,求大神解释 解决方案 看上去像简单异或加密,尝试下用原文xor base64解码后的密文,如果是一个常数,那么这个就是密码.

最长公共子序列|最长公共子串|最长重复子串|最长不重复子串|最长回文子串|最长递增子序列|最大子数组和

参考:http://www.ahathinking.com/archives/124.html 最长公共子序列 1.动态规划解决过程 1)描述一个最长公共子序列 如果序列比较短,可以采用蛮力法枚举出X的所有子序列,然后检查是否是Y的子序列,并记录所发现的最长子序列.如果序列比较长,这种方法需要指数级时间,不切实际. LCS的最优子结构定理:设X={x1,x2,--,xm}和Y={y1,y2,--,yn}为两个序列,并设Z={z1.z2.--,zk}为X和Y的任意一个LCS,则:       (1

算法-求助大神:c语言求最长公共子序列问题

问题描述 求助大神:c语言求最长公共子序列问题 我写的这个能正确求出最长序列元素个数但是输出的最长序列却是乱码,求大神指教.代码如下: #include #include #include #define MAX 101 int Long(char a[],char b[],char result[] ) { int m,n; m=strlen(a); n=strlen(b); int str[MAX][MAX]; int i,j,sum; for(i=0;i<=m;i++) { str[i][

文本比较算法Ⅶ——线性空间求最长公共子序列的Nakatsu算法

在参阅<A Longest Common Subsequence Algorithm Suitable for Similar Text Strings>(Narao Nakatsu,Yahiko Kambayashi,Shuzo Yajima著)后.发现该算法可以利用线性空间求出最长公共子序列.该算法的时间占用O(n(m-p+1)),p为最长公共子序列的长度.   字符串A和字符串B,计算LCS(A,B) 定义一:设M=Len(A),N=Len(B),不妨设M≤N. 定义二:A=a1a2--

已知一个二维数组,求一个新的二维数组,具体描述请看内容吧

问题描述 我将DataTable中的数据存放到了一个二维数组中,如图所示比如这个数组的名称是a[][],现在我定义一个新的二维数组b[][],求出a的每一行.每一列的和,然后和a一起,都赋值给b,b的结构如图所示.右下角是整个a数组的所有数据的和.这样的程序怎么写呢? 解决方案 解决方案二:唉,自己写for解决方案三:全部循环,简单暴力解决方案四:先看看....

[算法系列之十九]最长公共子序列

题目 最长公共子序列 分析 有两个字符串S1和S2,求一个最长公共子串,即求字符串S3,它们同时是S1和S2的子串,且要求它们的长度最长,并确定这个长度.这个问题我们称之为最长公共子序列问题. 与求最长递增子序列一样,我们首先将原问题分割成一些子问题,我们用dp[i][j]表示S1中前i个字符和S2中前j个字符分别组成的两个前缀字符串的最长公共子串长度.显然的,当i,j较小时我们可以直接给出答案,如dp[0][j] 必等于0.那么,假设我们已经求的dp[i][j](0 <= i < x,0 &