Java查找List最长递增序列 末尾元素未处理问题排查

原有代码核心问题 #

原有实现无法得到正确结果，本质是3个逻辑漏洞：

• 序列比较触发条件缺失：只有遍历到元素下降的位置才会比较暂存序列和结果的长度，如果最长递增序列出现在列表末尾、全程没有触发下降判断，这段序列永远不会被更新到结果中
• 元素收录逻辑错误：每次循环仅收录i-1位置的元素，既漏掉了每个递增段的尾部元素，还把temp清空逻辑错误嵌套在长度判断分支里，暂存序列比结果短时不会清空，会拼接后续无关元素造成数据污染
• 收尾逻辑缺失：循环遍历结束后，没有对最后一段暂存的递增序列做长度校验和结果更新

修正后可运行代码 #

public void findLongestSequence(List<Integer> values) {
    // 空列表边界处理
    if (values == null || values.isEmpty()) {
        System.out.println(values);
        System.out.println(new ArrayList<>());
        return;
    }
    List<Integer> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    // 初始化暂存序列，放入首个元素
    temp.add(values.get(0));
    for (int i = 1; i < values.size(); i++) {
        if (values.get(i) >= values.get(i - 1)) {
            // 处于递增区间，将当前元素加入暂存序列
            temp.add(values.get(i));
        } else {
            // 递增中断，先比较暂存序列与当前结果的长度
            if (temp.size() > result.size()) {
                result.clear();
                result.addAll(temp);
            }
            // 无论暂存序列长度是否超过结果，都重置暂存序列，以当前元素为起点记录新序列
            temp.clear();
            temp.add(values.get(i));
        }
    }
    // 补全收尾逻辑：比较最后一段暂存序列的长度，更新结果
    if (temp.size() > result.size()) {
        result.clear();
        result.addAll(temp);
    }
    System.out.println(values);
    System.out.println(result);
}

验证说明 #

使用测试用例List.of(7, 2, 7, 1, 2, 3, 8, 1, 2, 3, 4, 5)运行修正后的代码，最终输出的最长递增序列为[1, 2, 3, 4, 5]，与预期结果一致。

内容的提问来源于stack exchange，提问作者lap hoanglap