如何从给定的数组中打印最长的增加子序列(LIS)？

Question

我可以通过普通函数和递归函数打印LIS的长度.但我想在C++中打印给定数组中的LIS子序列索引.

这是我找到LIS长度的函数:

int lis( int *arr, int n )
{
   int *lis, i, j, max = 0;
   lis = (int*) malloc ( sizeof( int ) * n );
   for ( i = 0; i < n; i++ )
      lis[i] = 1;
   for ( i = 1; i < n; i++ )
      for ( j = 0; j < i; j++ )
         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;
   for ( i = 0; i < n; i++ )
      if ( max < lis[i] )
         max = lis[i];
   /* Free memory to avoid memory leak */
   free( lis );
   return max;
}

这里 array[10]={7 6 2 3 4 1 8 5 9 10}

这里 LIS Length=6

我想打印数字索引{2 3 4 6 8 9}(它不是序列,它的arrray索引,我想打印)序列索引array[10]

Answer 1

在为每个索引计算lis之后,取tmp值等于max,在lis数组上向后移动,并且每次找到等于max的元素时,将该索引添加到答案并减少tmp.因此,您将以相反的顺序获取索引数组.

示例代码:

int tmp = max;
std::vector<int> indexes;
for( i = n - 1; i >= 0; --i )
   if( lis[ i ] == tmp )
   {
      indexes.push_back( i );
      --tmp;
   }
std::reverse( indexes.begin(), indexes.end());