求递增最长子序列-非动态规划方式

你的名字 2022-12-30 12:55 186阅读 0赞

### 求递增最长子序列-非动态规划方式实现 ###

*   *  解题思路
     *  演示过程
     *  代码实现
     *  打印效果

> 学习Java的同学注意了！！！  
> 学习过程中遇到什么问题或者想获取学习资源的话，欢迎加入Java学习交流群，群号码：543120397 我们一起学Java！

> 需求描述：给定一个int数组，【0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15】，求所有的递增最长子序列。

## 解题思路 ##

1.从最后索引位置，往前遍历。  
2.每遍历一个元素，汇总当前组最长递增子序列。  
3.所有循环结束后，再求最后集合中的最长递增子序列。

## 演示过程 ##

*         解题思路:(保留每一组的max即可)
     *         //15(max) (单个被使用后应当舍弃)
     *
     *         //7 15(max) (下一个索引位置,只拼接最长的列)
     *
     *         //11 15(max)
     *
     *         //3 15
     *         //3 7 15(max)
     *
     *         //13 15(max)
     *
     *         //5 13 15(max)
     *         //5 11 15(max)
     *         //5 7 15(max)
     *         //5 15
     *
     *         //9 13 15(max)
     *         //9 11 15(max)
     *         //9 15
     *
     *         //1 9 11 15(max)
     *         //1 9 13 15(max)
     *         //1 5 7 15(max)
     *         //1 5 11 15(max)
     *         //1 5 13 15(max)
     *         //1 13 15
     *         //1 3 7 15
     *         //1 11 15
     *         //1 7 15
     *         //1 15
     *
     *         //14 15(max)
     *
     *         //6 9 11 15(max)
     *         //6 9 13 15(max)
     *         //6 11 15
     *         //6 7 15
     *         //6 15
     *
     *         //10 14 15(max)
     *         //10 13 15(max)
     *         //10 11 15(max)
     *         //10 15
     *
     *         //2 10 11 15
     *         //2 10 13 15
     *         //2 10 14 15
     *         //2 6 9 13 15(max)
     *         //2 6 9 11 15(max)
     *         //2 14 15
     *         //2 9 11 15
     *         //2 9 13 15
     *         //2 5 7 15
     *         //2 5 11 15
     *         //2 5 13 15
     *         //2 13 15
     *         //2 3 7 15
     *         //2 11 15
     *         //2 7 15
     *         //2 15
     *
     *         //12 14 15(max)
     *         //12 13 15(max)
     *         //12 15
     *
     *         //4 12 13 15
     *         //4 12 14 15
     *         //4 10 11 15
     *         //4 10 13 15
     *         //4 10 14 15
     *         //4 6 9 13 15(max)
     *         //4 6 9 11 15(max)
     *         //4 9 11 15
     *         //4 9 13 15
     *         //4 5 7 15
     *         //4 5 11 15
     *         //4 5 13 15
     *         //4 13 15
     *         //4 11 15
     *         //4 7 15
     *         //4 15
     *
     *         //8 12 13 15(max)
     *         //8 12 14 15(max)
     *         //8 10 11 15(max)
     *         //8 10 13 15(max)
     *         //8 10 14 15(max)
     *         //8 14 15
     *         //8 9 11 15(max)
     *         //8 9 13 15(max)
     *         //8 13 15
     *         //8 11 15
     *         //8 15
     *
     *         //0 8 9 13 15
     *         //0 8 9 11 15
     *         //0 8 10 14 15
     *         //0 8 10 13 15
     *         //0 8 10 11 15
     *         //0 8 12 14 15
     *         //0 8 12 13 15
     *         //0 4 6 9 11 15(max)
     *         //0 4 6 9 13 15(max)
     *         //0 12 13 15
     *         //0 12 14 15
     *         //0 2 6 9 11 15(max)
     *         //0 2 6 9 13 15(max)
     *         //0 10 11 15
     *         //0 10 13 15
     *         //0 10 14 15
     *         //0 6 9 13 15
     *         //0 6 9 11 15
     *         //0 14 15
     *         //0 1 5 13 15
     *         //0 1 5 11 15
     *         //0 1 5 7 15
     *         //0 1 9 13 15
     *         //0 1 9 11 15
     *         //0 9 11 15
     *         //0 9 13 15
     *         //0 5 7 15
     *         //0 5 11 15
     *         //0 5 13 15
     *         //0 13 15
     *         //0 3 7 15
     *         //0 11 15
     *         //0 15

## 代码实现 ##

public static void main(String[] args){ 
        int[] origin = new int[]{ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
        List<int[]> maxLen = getMaxLen(origin);
        for (int[] ints : maxLen) { 
            System.out.println(Arrays.toString(ints));
        }
    }
    
    /** * 求int数组的递增最长子序列 * 1.只根据同组中,最长的组合即可(一组中,只有一列的保留,其它的保留最长的即可,如果最长有很多,保留多个) * 2.从后往前遍历 * 3.最后求最长子数组长度,得出最长子序列 * * * 0 4 6 9 11 15 * 0 4 6 9 13 15 * 0 2 6 9 11 15 * 0 2 6 9 13 15 * @param origin 原int数组 * @return 最长子序列 */
    private static List<int[]> getMaxLen(int[] origin) { 
        //收集所有的小组中的最长数组
        List<int[]> list = new ArrayList<>();
    
        for (int index = origin.length - 1; index >= 0 ; index--){ 
            handler(list, origin[index]);
        }
    
        return getMaxSubSequence(list);
    }
    
    
    /** * 添加一个元素 * @param list 目标list对象,用来存储二维数组 * @param currentElement 当前元素 */
    private static void handler(List<int[]> list, int currentElement) { 
        //针对第一个元素
        int[] innerData;
        if(list.size() == 0){ 
            innerData = new int[]{ currentElement};
            list.add(innerData);
        }else{ 
            List<int[]> tempArr = new ArrayList<>();//用来记录,currentElement进来后,产生的临时数组
            for (int[] getElement : list) { 
                //确保能取到第一个元素
                if (getElement != null && getElement.length > 0) { 
                    if (currentElement <= getElement[0]) { //只有currentElement小于等于首位元素的值,才能拼接起来
                        int[] mini = new int[getElement.length + 1];//增加一个位置
                        mini[0] = currentElement;//首位设置成当前值
                        //getElement从首位开始
                        System.arraycopy(getElement, 0, mini, 1, mini.length - 1);
                        tempArr.add(mini);//将构建好的元素加入临时tempArr中
                    }
                }
            }
            //保留临时数组中,长度最长的递增序列
            List<int[]> remainArr = getMaxSubSequence(tempArr);
            list.addAll(remainArr);
        }
    }
    
    /** * 获取集合中,长度最长的子序列 * @param tempArr 数组 * @return 结果 */
    private static List<int[]> getMaxSubSequence(List<int[]> tempArr) { 
        List<int[]> arr = new ArrayList<>();
        if(tempArr.size() == 1){ //如果只有一个元素,直接返回即可
            return tempArr;
        }
        int max = 0;
        for (int[] ints : tempArr) { //这一轮遍历,获取最大长度
            if (ints.length > max) { 
                max = ints.length;
            }
        }
        for (int[] ints : tempArr) { //这一轮遍历,保留最长子序列
            if (ints.length == max) { 
                arr.add(ints);
            }
        }
        return arr;
    }

## 打印效果 ##

[0, 2, 6, 9, 11, 15]
    [0, 2, 6, 9, 13, 15]
    [0, 4, 6, 9, 11, 15]
    [0, 4, 6, 9, 13, 15]