算法研究：已知不重复的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个多小时写这段代码,感觉这道题重要的难点就是不连续的子集合这点，因为所有子集合数量应该是集合大小的阶乘。但是递增子集合就会少很多。