最長的子序列數

Question

我需要返回數組的LIS。

僞例如：

if the arr is 
int []arr = {2,4,90,-3,-2,-1,-10,-9,-8}; 
num of LIS is: 3 
2,4,90 
-3,-2,-1 
-10,-9,-8 

例子2：

arr [] = {2,-3,4,90,-2,-1,-10,-9,-8}; 
num of LIS is: 4 
2,4,90 
-3,4,90 
-3,-2,-1 
-10,-9,-8 

我試圖做到這一點：

int [] A = {2,4,90,-3,-2,-1,-10,-9,-8}; 
    int[] dp = new int[A.length]; 

    for (int i = 0; i < A.length; i++) { 
     dp[i] = 1; 

     for (int j = 0; j <= i - 1; j++) { 
      if (A[j] < A[i]) { 
       dp[i] = dp[i] + dp[j]; 
      } 
     } 
     System.out.println(dp[dp.length - 1]) ; 
    } 

Answer 1

在你的代碼只是不斷加入到DP [我]在inner for循環中查找所有查找。理想情況下，您應該找到所有職位的子序列的最大大小（j < i），然後將該最大值添加到d [i]。 正確的方法如下：

int maxSizeOfSubseq = 0; 
for (int i = 0; i < A.length; i++) { 
    dp[i] = 1; 
    maxSizeOfSubseq = 0; 
    for (int j = 0; j <= i - 1; j++) { 
     if (A[j] < A[i] && dp[j] > maxSizeOfSubseq) { 
      maxSizeOfSubseq = dp[j]; 
     } 
    } 
    dp[i] = dp[i] + maxSizeOfSubseq ; 
      System.out.println(dp[dp.length - 1]) ; 
} 


// Now find the Max Size Of Subsequence amongst all computes subsequence lengths 
maxSizeOfSubseq = 0; 
for(int count = 0 ; count < dp.length; ++count) 
{ 
    if(dp[i] > maxSizeOfSubseq) 
    { 
    maxSizeOfSubseq = dp[i] 
    } 
} 

return maxSizeOfSubseq ;