如何打印来自给定数组的最长增量子序列（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()); 

Answer 2

，以便您可以使用递归方法打印：调用：printLIS（LIS，lis.length -1，编曲，最大值）

public static void printLIS(int[] lis, int lisIndex, int[] arr, int max) { 
    if(max == 0) { 
     return; 
    } 
    if(lis[lisIndex] == max) { 
     printLis(lis,lisIndex-1, arr, max-1); 
     System.out.print(arr[lisIndex] + " "); 
    } else { 
     printLis(lis,lisIndex-1, arr, max); 
    } 

} 

Answer 3

int lis(int *arr, int n) 
{ 
    int *lis, i, j, max = 0, max_index = 0; 
    int *print = (int*)malloc(sizeof(int)*n); 
    lis = (int*) malloc (sizeof(int) * n); 
    for (i = 0; i < n; i++){ 
     lis[i] = 1; 
     print[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; 
      print[i] = j; 
     } 
    for (i = 0; i < n; i++){ 
     if (max < lis[i]){ 
     max = lis[i]; 
     max_index = i; 
     } 
    } 
    while(max_index >=0){ 
     printf("%d ",lis[max_inc_index]); 
     max_index = print[max_index]; 
    } 
    /* Free memory to avoid memory leak */ 
    free(lis); 

    return max; 
} 

使用额外的数组跟踪索引，这是最长的子序列的一部分，然后遍历数组以打印所有相应的元素。

Answer 4

可以声明一个动态数组，其长度等于递增序列的最大长度。数组ANS将保持最长的递增顺序。

int *ans=(int*)malloc(sizeof(int)*max); 

临时变量用于保持数组中最大长度的索引。

int index; 
    int length; //used to fill array ANS in reverse order. 
    for (i = 0; i < n; i++) 
     { 
      if (max < lis[i]) 
      { 
       max = lis[i]; 
       index=i; 
      } 
     } 
    length=max; 
    ans[length-1]=arr[index]; //filling array from the last 
           //last element will be the greatest element 
    length--; 
    while(index>0) 
    { 
     for(i=index-1;i>=0;i--) 
     { 
      if(lis[i]+1==lis[index] && arr[i]<arr[index]) 
      { 
       ans[length-1]=arr[i]; 
       index=i; 
       length--; 
       break; 
      } 
     } 
    } 
    for(i=0;i<max;i++) 
    { 
     printf("%d",ans[i]); 
    } 

这里的复杂度为O（N），而不是O（N2），即使它可能使用两个环路，如果输入块每当因为我们正在改变指数的价值我。