使用蛮力方法在列表中查找最长的非递减子集？

Question

我们有一个数字列表 (5, 12, 4, 6, 7, 12, 5, 55, 13, 14) 我必须找到最大的非递减子集 (4, 6, 7, 12) .

同样应该通过暴力破解的方式来解决。我试图解决它，但我不确定这是一个蛮力解决方案。任何提示都会有所帮助！（伪代码，java 代码或任何帮助...）

  public static void main(String[] args) {
            int[] nonDecrease = { 5, 12, 4, 6, 7, 12, 5, 55, 13, 14 };
            ArrayList list = new ArrayList();
            ArrayList temp = new ArrayList();
            list.add(nonDecrease[0]);

            int counter = 0;
            int a = 0;

             for (int i = 1; i < nonDecrease.length; i++) {
                if (nonDecrease[i - 1] < nonDecrease[i]) {
                    list.add(nonDecrease[i]);
                    counter = list.size();
                } else if (nonDecrease[i - 1] > nonDecrease[i] && counter >= a) {
                    a = list.size();

                    if (list.size() >= temp.size() && counter >= a) {
                        temp = list;
                        System.out.println(temp + "t");
                    }
                    list.clear();
                    list.add(nonDecrease[i]);
                }
            }
        }
    }

Answer 1

有了bruteforce，你可以试试这个方法。请注意，您有 maxLength = maxList.size()，因此您不必存储额外的 maxLength 变量。

List<Integer> maxList = new ArrayList(); 

for (int i = 0; i < nonDecrease.length - 1;) {
   int prev = nonDecrease[i];
   List<Integer> currentMaxList = new ArrayList();
   currentMaxList.add(prev);

   int j = i + 1;
   for (; j < nonDecrease.length; j++) {
      if (nonDecrease[j] >= prev) {
          prev = nonDecrease[j];
          currentMaxList.add(prev);
      } else {
          break;
      }
   }
   if (currentMaxList.size() > maxList.size()) {
      // Found new longer
      maxList = currentMaxList;
   }
   // The non-decreasing break at `j` so we continue the next search at j:
   i = j;
}

使用蛮力方法在列表中查找最长的非递减子集？

Finding the biggest nondecreasing Subset in a list using Brute Force approach?

java

algorithm

dynamic-programming

brute-force