algorithm - 最长递增子序列(O(nlogn))

LIS:wikipedia

我无法理解的一件事是:

为什么X [M [i]]是不递减的序列？

最佳答案

让我们首先看一下n ^ 2算法:

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非常特殊，c [i]的意思是:最长递增序列的最后一个元素的最小值，其长度为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;
   }
}