Вопросы с самым продолжительным возрастанием подпоследовательности - наивный подход

Question

Я изучал основы динамического программирования и подошел к question, чтобы найти самую длинную нарастающую подпоследовательность в массиве. Прежде чем искать решение DP, я решил сам его закодировать и придумал следующий алгоритм, полный код которого можно найти here.

Идея состоит в создании массива-списка для хранения всех возрастающих подпоследовательностей и сохранения соответствующего максимального значения каждой подпоследовательности для более быстрого сравнения.

private void findLIS(int[] inputArr) { 
    List[] listOfSubs = new ArrayList[inputArr.length]; //Max different subsequences in an array would be N 
    //To store the max value of each of the subsequences found yet 
    List<Integer> maxValList = new ArrayList<Integer>(); 
    listOfSubs[0] = new ArrayList<Integer>(); 
    listOfSubs[0].add(inputArr[0]); //Add the first element of the array to the list 
    maxValList.add(inputArr[0]); 

    for (int i=1;i<inputArr.length;i++) { 
     boolean flag = false; 
     int iter=0; 

     //Compare inputArr[i] with the maxVal of each subsequence 
     for (int j=0; j<maxValList.size(); j++) { 
      if (inputArr[i]>maxValList.get(j)) { 
       maxValList.set(j, inputArr[i]); //Update the maxVal in the corresponding position in the list 
       listOfSubs[j].add(inputArr[i]); 
       flag = true; 
      } 
      iter = j; 
     } 
     //If inputArr[i] is not greater than any previous values add it to a new list 
     if (!flag) { 
      maxValList.add(inputArr[i]); 
      listOfSubs[iter+1] = new ArrayList<Integer>(); 
      listOfSubs[iter+1].add(inputArr[i]); 
     } 
    } 

    //Finding the maximum length subsequence among all the subsequences 
    int max=0, iter=0, index=0; 
    for (List<Integer> lst : listOfSubs) { 
     if (lst!=null && lst.size() > max) { 
      max = lst.size(); 
      index=iter; 
     } 
     iter++; 
    } 

    //Print the longest increasing subsequence found 
    System.out.println("The Longest Increasing Subsequence is of length " + listOfSubs[index].size() + 
      " and is as follows:"); 
    for (int i=0;i<listOfSubs[index].size();i++) { 
     System.out.print(listOfSubs[index].get(i) + " "); 
    } 
} 

Код работает в O (n^2) и отлично работает для ввода малых/средних размеров. Однако, когда я пытаюсь запустить код с некоторыми порталами онлайн-практики (например, HackerRank), я получаю как TLE (превышение времени превышения ошибок), так и неправильный ответ. Я понимаю ошибки TLE, поскольку эффективное решение - это решение DP O (nlogn), но я смущен неправильными ответами, генерируемыми этим алгоритмом. Поскольку входы для таких случаев слишком большие (~ 10000), я не могу вручную проверить, где решение идет не так.

Полный код плюс вывод на один из наборов данных можно найти here. Правильный ответ должен быть равен 195, как сообщает HackerRank.

Answer 1

Я нашел проблему с моим решением. Проблема заключается в том, что вы не внимательно читаете заявление о проблеме.

Скажем, мы рассматриваем ввод как {3, 2, 6, 4, 5, 1}. Я рассматриваю только последовательности {3,6} и {2,6} в моем коде, но не последовательности {2,4,5} или {3,4,5}. Таким образом, на каждой итерации, если я нахожу число, большее, чем максимум предыдущих подпоследовательностей, я добавляю его ко всем таким подпоследовательностям, тем самым уменьшая возможность достижения последних подпоследовательностей.