题解 | #最长递增子序列#

import java.util.*;

//部分答案正确，超时，动态规划 public class Solution { /** * retrun the longest increasing subsequence * @param arr int整型一维数组 the array * @return int整型一维数组 */ public int[] LIS (int[] arr) { // write code here int length = arr.length; if(length == 0){ return null; }

    int[][] dp = new int[length][2];
    for(int i=0;i<length;i++){
        dp[i][0] = 1;//dp[i]表示以arr[i]这个数结尾的最长递增子序列的长度
        dp[i][1] = 0;//存放上一节点的索引
    }
    int min = 0;
    for(int i = 0;i<length;i++){
        min = arr[i];
        for(int j = 0;j<i;j++){
            if(arr[j]<arr[i]){
                if(dp[i][0]<=dp[j][0]+1){
                    dp[i][0] = dp[j][0]+1;
                    if(arr[j]<min){
                        dp[i][1] = j;
                    }
                }
            }
        }
    }
    
    int maxLength = dp[0][0];
    int index = 0;
    for(int i =1;i<length;i++){
        if(dp[i][0]>=maxLength){
            maxLength = dp[i][0];
            index = i;
        }
    }
    
    int[] c = new int[maxLength];
    for(int i = maxLength-1;i>=0;i--){
        c[i] = arr[index];
        index = dp[index][1];
    }
    
    return c;
}

}