數據結構與演算法：動態規劃之LIS最長遞增子序列

給定數組arr,返回arr的最長遞增子序列長度，比如arr=[2,1,5,3,6,4,8,9,7],那麼最長遞增子序列為[1,3,4,8,9] ]，所以返回這個最長遞增子序列的長度5。

基本思路就是創建dp[]數組，每個位置記錄該位置的最長遞增子序列

可以發現遞推關係就是當你檢測arr[i]處時，向前遍歷，當出現比arr[i]小的元素時，從這些小的元素中選出對應dp[j]最大的作為maxLength.然後dp[i]=maxLength+1;

以此類推。

動態規劃：

①創建動態規劃數組保留每個計算結果，這裡只需要一維數組dp[n];

②先計算dp[]中第一個位置的值，即dp[0]，即以arr[0]為終點的最長遞增子序列的最大子序列長度是1；

③從前往後計算dp[]中的每一個位置的值；注意遞推關係的使用；

④掃描dp[]，裡面的最大值就是所求結果；

具體Java代碼：

public int getLIS(int[] arr, int n) { if(arr==null||arr.length<=0) return 0; //創建dp數組 int[] dp=new int[arr.length]; dp[0]=1; for(int i=1;i<arr.length;i++){ //每次都需要置零 int maxLength=0; for(int j=0;j<i;j++){ //如果出現比i元素小的，則記錄該j對應的dp[j],選取最大的dp[j] if(arr[j]<arr[i]){ maxLength=Math.max(maxLength, dp[j]); } } dp[i]=maxLength+1; } int maxResult=0; for(int i=0;i<dp.length;i++){ maxResult=Math.max(maxResult, dp[i]); } return maxResult; }

上述的僅僅是返回最大的長度。

我們接下來要實現返回這個子序列：

思路是，創建二維數組lessArr存儲最長子序列每次檢測完maxLength之後，找出maxLength對應dp數組中的位置index，然後進行覆蓋至maxLength前一個位置，然後lessArr[i][maxLength]=arr[i],將該元素加入進去。

public static int getLIS(int[] arr) { if(arr==null||arr.length<=0) return 0; //創建dp數組,存儲最長子序列長度 int[] dp=new int[arr.length]; dp[0]=1; //創建lessArr數組，存儲最長子序列 int[][] lessArr=new int[arr.length][arr.length]; lessArr[0][0]=arr[0]; for(int i=1;i<arr.length;i++){ //每次都需要置零 int maxLength=0; int index=0;//記錄選取的最大的dp[j]對應的下標 for(int j=0;j<i;j++){ //如果出現比i元素小的，則記錄該j對應的dp[j],選取最大的dp[j] if(arr[j]<arr[i]){ maxLength=Math.max(maxLength, dp[j]); } } //找出maxLength對應下標 for(int m=0;m<i;m++){ if(maxLength==dp[m]){ index=m; } } //將以元素j結尾的最長遞增子序列拷貝到以元素i結尾的最長遞增子序列中 for(int k=0;k<maxLength;k++){ lessArr[i][k]=lessArr[index][k]; } lessArr[i][maxLength]=arr[i]; dp[i]=maxLength+1; } //測試子序列// shuchu(lessArr); int maxResult=0; for(int i=0;i<dp.length;i++){ maxResult=Math.max(maxResult, dp[i]); } return maxResult; }

但是上述方法可以發現，這樣只能得到一個子序列。

但對於上面那個例子：arr=[2,1,5,3,6,4,8,9,7],我們其實可以發現最長遞增子序列長度為5的序列有[1,3,6，8,9] 、[2,3,6,8,9]等。但是只能輸出一個。

網上也查閱了很多資料。

暫時還沒有得到輸出全部子序列的思路。

後續更新。