是否有NlogN解来找到最长的递增子序列？

Question

我正在HackerRank上解决this problem，但是使用O（n ^ 2） DP方法获得了TLE。

如果有人可以指导完成O（NLogN）解决方案的工作，那就太好了。找不到很好的解释。

Answer 1

解决O（n ^ 2）中最长增长子序列的通用方法是：

for (int k = 0; k < n; k++) {
  length[k] = 1;
  for (int i = 0; i < k; i++) {
      if (array[i] < array[k]) {
          length[k] = max(length[k],length[i]+1);
      }
   }
}

一旦您了解了这一点，就可以轻松理解O（logN）。您可以找到O（logN）方法here。