获取数组所有最长升序子序列的Java代码问题排查

问题根源 #

原数组中存在重复元素（比如多个1、2、3），导致生成最长升序子序列时，不同索引路径会生成完全相同的序列，最终重复加入结果列表。

解决思路 #

核心是在序列生成阶段避免重复路径，而非事后去重（事后去重效率更低）。通过动态规划+回溯的组合方式，在回溯过程中跳过会产生重复序列的分支：

• 先计算每个位置结尾的最长升序子序列长度（dp数组），确定最长子序列的长度
• 回溯收集最长子序列时，遇到相同元素且对应dp值相同的情况，跳过当前分支（相同元素的前一个分支已处理过相同的序列生成逻辑）

具体Java实现 #

import java.util.*;

public class LongestIncreasingSubsequences {
    public static List<List<Integer>> findAllLongestIncreasingSubsequences(int[] nums) {
        int n = nums.length;
        if (n == 0) return new ArrayList<>();
        
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 1;
        
        // 计算dp数组，确定最长子序列长度
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        List<List<Integer>> result = new ArrayList<>();
        // 回溯收集所有最长子序列，同时去重
        backtrack(nums, dp, maxLen, n - 1, new ArrayList<>(), result);
        
        return result;
    }
    
    private static void backtrack(int[] nums, int[] dp, int targetLen, int index, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == targetLen) {
            // 反转得到升序序列
            List<Integer> temp = new ArrayList<>(current);
            Collections.reverse(temp);
            result.add(temp);
            return;
        }
        
        for (int i = index; i >= 0; i--) {
            // 去重关键：相同元素且dp值相同时，跳过当前分支
            if (i < index && nums[i] == nums[i + 1] && dp[i] == dp[i + 1]) {
                continue;
            }
            if (dp[i] == targetLen - current.size()) {
                current.add(nums[i]);
                backtrack(nums, dp, targetLen, i - 1, current, result);
                current.remove(current.size() - 1);
            }
        }
    }
    
    public static void main(String[] args) {
        int[] nums = {1,2,1,2,3,1,3,7};
        List<List<Integer>> result = findAllLongestIncreasingSubsequences(nums);
        System.out.println(result); // 输出 [[1,2,3],[1,3,7]]
    }
}

代码说明 #

1. DP数组计算：dp[i]表示以nums[i]结尾的最长升序子序列长度，遍历数组确定最长子序列的长度maxLen。
2. 回溯去重逻辑：在回溯循环中，当nums[i]等于nums[i+1]且两者的dp值相同时，跳过当前i的分支——因为i+1的位置已经处理过相同元素的序列生成，再处理i会生成重复序列。
3. 序列反转：回溯时从后往前收集元素，最后反转得到升序的子序列。

内容的提问来源于stack exchange，提问作者Ivan Dvurechenskiy