Найти самое большое неубывающее подмножество в списке, используя метод грубой силы

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;
}