如何用暴力法查找数组中的最大非递减子集？现有代码求验证

你好！咱们先明确需求：给定数组 (5, 12, 4, 6, 7, 12, 5, 55, 13, 14)，要找出其中的最大非递减子集（你提到的示例是(4, 6, 7, 12)），并且要求用暴力法实现。先看你写的这段代码，它其实不属于暴力法——你的思路是遍历数组时维护当前的非递减序列，遇到下降就比较长度，这更像是一次遍历的贪心思路，但暴力法的核心是枚举所有可能的子集，再筛选符合条件的最长那个。

先给你拆解下暴力法的核心逻辑：

• 枚举数组中所有可能的子序列（注意这里的子集是指元素保持原顺序的子序列，不是任意组合）
• 对每个子序列，检查它是否是非递减的
• 记录所有符合条件的子序列中长度最长的那个

暴力法的伪代码 #

初始化最长非递减子序列为空
遍历数组中每个起始索引i从0到n-1：
    初始化当前子序列为[arr[i]]
    遍历每个结束索引j从i+1到n-1：
        如果arr[j] >= 当前子序列的最后一个元素：
            将arr[j]加入当前子序列
            如果当前子序列长度 > 最长子序列长度：
                更新最长子序列为当前子序列的副本
        否则：
            继续下一个j（如果是找连续子数组则break，不连续则跳过）
    单独检查单个元素的情况（避免遗漏）
返回最长非递减子序列

你的代码问题分析 #

你的代码逻辑是在一次遍历中，遇到递增就追加元素，遇到递减就保存当前序列并重置，但这种方法会错过很多可能的非递减子序列。比如数组中的(5,12,55)或者(4,6,7,12,55)这类候选，而且核心是没有枚举所有可能的组合，不符合暴力法的定义。

暴力法的Java代码示例 #

针对连续非递减子数组的暴力实现

如果你的需求是找连续的最长非递减子数组（和你给出的示例匹配），代码如下：

import java.util.ArrayList;
import java.util.List;

public class LongestContinuousNonDecreasing {
    public static void main(String[] args) {
        int[] arr = {5, 12, 4, 6, 7, 12, 5, 55, 13, 14};
        List<Integer> longestSubset = findLongestContinuousNonDecreasing(arr);
        System.out.println("最长连续非递减子集：" + longestSubset);
    }

    public static List<Integer> findLongestContinuousNonDecreasing(int[] arr) {
        List<Integer> longest = new ArrayList<>();
        int n = arr.length;

        // 枚举所有起始位置
        for (int i = 0; i < n; i++) {
            List<Integer> current = new ArrayList<>();
            current.add(arr[i]);
            // 从起始位置往后扩展连续子数组
            for (int j = i + 1; j < n; j++) {
                if (arr[j] >= current.get(current.size() - 1)) {
                    current.add(arr[j]);
                } else {
                    // 连续子数组中断，跳出循环
                    break;
                }
            }
            // 更新最长序列
            if (current.size() > longest.size()) {
                longest = new ArrayList<>(current);
            }
        }
        return longest;
    }
}

针对不连续非递减子序列的暴力实现

如果是找不连续的最长非递减子序列，暴力法需要用回溯枚举所有可能的组合（时间复杂度O(2^n)，非常低效，但符合暴力法定义）：

import java.util.ArrayList;
import java.util.List;

public class LongestNonDecreasingSubsequence {
    private static List<Integer> longest;

    public static void main(String[] args) {
        int[] arr = {5, 12, 4, 6, 7, 12, 5, 55, 13, 14};
        longest = new ArrayList<>();
        backtrack(arr, 0, new ArrayList<>());
        System.out.println("最长非递减子序列：" + longest);
    }

    private static void backtrack(int[] arr, int start, List<Integer> current) {
        // 更新最长序列
        if (current.size() > longest.size()) {
            longest = new ArrayList<>(current);
        }

        for (int i = start; i < arr.length; i++) {
            // 满足非递减条件则加入当前序列
            if (current.isEmpty() || arr[i] >= current.get(current.size() - 1)) {
                current.add(arr[i]);
                backtrack(arr, i + 1, current);
                current.remove(current.size() - 1); // 回溯，尝试其他组合
            }
        }
    }
}

总结 #

你的代码是一次遍历的贪心策略，不属于暴力法。暴力法的核心是枚举所有可能的候选子序列，再逐一验证筛选，虽然效率低，但完全符合暴力法“穷尽所有可能”的定义。根据你的需求选择对应的实现即可。

内容的提问来源于stack exchange，提问作者john tame