最长递增子（O（nlogn）） [英] longest increasing subsequence(O(nlogn))

问题描述

LIS：维基百科

还有一件事，我不明白：

There is one thing that I can't understand:

为什么X [M [我]一个非递减顺序？

why is X[M[i]] a non-decreasing sequence?

推荐答案

让我们先来看看第n ^ 2算法：

Let's first look at the n^2 algorithm:

dp[0] = 1;
for( int i = 1; i < len; i++ ) {
   dp[i] = 1;
   for( int j = 0; j < i; j++ ) {
      if( array[i] > array[j] ) {
         if( dp[i] < dp[j]+1 ) {
            dp[i] = dp[j]+1;
         }
      }
   }
}

现在的改善发生在第二循环中，基本上，你可以通过使用二进制搜索提高速度。除了DP []数组，让我们有另一个数组c []，c是pretty的特殊，C [I]表示：最长递增序列的长度是我的最后一个元素的最低值

Now the improvement happens at the second loop, basically, you can improve the speed by using binary search. Besides the array dp[], let's have another array c[], c is pretty special, c[i] means: the minimum value of the last element of the longest increasing sequence whose length is i.

sz = 1;
c[1] = array[0]; /*at this point, the minimum value of the last element of the size 1 increasing sequence must be array[0]*/
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
   if( array[i] < c[1] ) {
      c[1] = array[i]; /*you have to update the minimum value right now*/
      dp[i] = 1;
   }
   else if( array[i] > c[sz] ) {
      c[sz+1] = array[i];
      dp[i] = sz+1;
      sz++;
   }
   else {
      int k = binary_search( c, sz, array[i] ); /*you want to find k so that c[k-1]<array[i]<c[k]*/
      c[k] = array[i];
      dp[i] = k;
   }
}

这篇关于最长递增子（O（nlogn））的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！