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

悠悠 2022-07-12 07:51 85阅读 0赞

问题背景：最近换工作面试，面试官问了一道编程题，大体是已知不重复的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个多小时写这段代码,感觉这道题重要的难点就是不连续的子集合这点，因为所有子集合数量应该是集合大小的阶乘。但是递增子集合就会少很多。