题解 | #最长上升子序列(一)#

另一种思路，先排序，然后求最长公共子序列。这里怎么说：

2 3 2 1 5 -》排序后：1 2 2 3 5，

求 1 2 2 3 4与2 3 2 1 5的最长公共子序列，得到的即是最长上升子序列，这里排序是为了满足上升的需求

时间复杂度为 n^2 空间复杂度 n^2

import java.util.*;


public class Solution {

    public int LIS (int[] arr) {
        int length = arr.length;
        int[] time = new int[length];
        System.arraycopy(arr, 0, time, 0, length);
        Arrays.sort(time);
        int[][] lcs = new int[length+1][length+1];
        for(int i = 1; i <= length; i++){
            for(int j = 1; j <= length; j++){
                if(arr[i - 1] == time[j - 1]) lcs[i][j] = lcs[i-1][j-1] + 1;
                else lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
            }
        }
        return lcs[length][length];
    }
}