c++ - 如何从给定数组打印最长递增子序列 (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} (它不是序列，它是数组索引，我想打印什么)数组中的序列索引[ 10]

Answer 1

在为每个索引计算完 lis 后，取一个等于 max 的 tmp 值，在 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());