要找到給定的整數數組所有最長遞增子序列 - 動態規劃

Question

我學習動態編程&我碰到這個問題，在我所要打印出所有的最長子序列來了。有可能是給定一個數組不止一個最長子。 ，我試圖程序會給我只有一個最長子但不是所有的最長子。我如何獲得所有最長的子序列？

//Initially I create two arrays of the length of the given input array 

public static void LIS(int[] input) { 

    String paths[] = new String[input.length]; 
    int[] size = new int[input.length]; 

    for(int i=0;i<input.length; i++) { 
     paths[i] = input[i]; 
     size[i] = 1; 
    } 

    for(i=1; i<input.length ; i++) { 

     for(j=i; j< i ; j++) { 
      if(input[i] > input[j] && size[i] < size[j] + 1) { 
       size[i] = size[j] +1; 
       paths[i] = paths[j] + input[i] + "" 

       if (maxlength < size[i]) { 
        maxlength = size[i]; 
       } 
      } 
     } 
    } 
} 

我的示例輸入[] = 1,8,10,3,7,12,15

與上述算法我得到的最長子如1,8,10,12,15

我還應該得到1,3,7,12,15

我該如何修改代碼才能得到它？

Answer 1

如果要修改這個代碼，你可以存儲任何元素的所有可能的前輩; 從代碼：

for(i=1; i<input.length ; i++) { 

    for(j=i; j< i ; j++) { 
     //if(input[i] > input[j] && size[i] < size[j] + 1) { 
     if(input[i] > input[j] && size[i] <= size[j] + 1) { 
      size[i] = size[j] +1; 
      //paths[i] = paths[j] + input[i] + "" 
      if (size[i] < size[j] + 1) 
       //empty p[i] 
      p[i].push(j); 

      if (maxlength < size[i]) { 
       maxlength = size[i]; 
      } 
     } 
    } 
} 

，然後你需要恢復所有可能的子序列