如何打印來自給定數組的最長增量子序列（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），即使它可能使用兩個環路，如果輸入塊每當因爲我們正在改變指數的價值我。