最长递增子序列

原数组 arr    [4 2 3 1 5]

 LinkedList<Integer> vec ；

i        arr            vec
0         4  	         4     //直接添加
1	  2		 2    // 2小于4 替换掉4
2	  3		 2 3  //直接添加
3	  1		 1 3  //  1 小于 2  替换。  即  arr[i] 替换掉  vec中  第一个比 arr[i]大的元素。
4	  5		 1 3 5  

vec 最后的长度即是 LIS 的长度。但vec  不一定是最终的 最大上升子序列，即LIS 

maxLen[] ** 表示以 i 结尾的最长递增子序列长度**。

举个例子 arr [4,2,3,1,5]  对应的  maxLen[] 是 [1,1,2,1,3];

public class S10 {
    public static int[] LIS(int[] arr) {
        //只有一个元素 直接返回
        if (arr.length==1){
            return  arr;
        }
     
        LinkedList<Integer> vec = new LinkedList<>();
        int[] maxLen = new int[arr.length];
        vec.add(arr[0]);
        maxLen[0] = 1;
        //求vec 和 maxLen[]
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > vec.getLast()) {
                vec.add(arr[i]);
                maxLen[i] = vec.size();
            } else if (arr[i] < vec.getLast()) {
                Iterator<Integer> iterator = vec.iterator();
                int j = 0;
                while (iterator.hasNext()) {
                    Integer next = iterator.next();
                    j++;
                    if (next >= arr[i]) {
                        vec.set(j - 1, arr[i]);
                        break;
                    }
                }
                maxLen[i] = j;
            } else {
                maxLen[i] = vec.size();
            }
        }
		//通过maxLen 和 Vec 计算 最大上升子序列。
        int max = vec.size();
        int[] res = new int[max];
        int k = max - 2;
        boolean f = false;
        int left = 0;
        for (int i = arr.length - 1; i > 0; i--) {
            if (!f && vec.size() == maxLen[i]) {
                f = true;
                res[max - 1] = arr[i];
                left = maxLen[i];
            }
            if (f) {
                if (left - maxLen[i - 1]==1 && maxLen[i - 1] < max) {
                    max--;
                    res[k] = arr[i - 1];
                    k--;
                    left--;
                }
            }

        }
        return res;

    }

    public static void main(String[] args) {
        int[] arr = {1,3,8,6,5,2,5};
        int[] lis = LIS(arr);
        for (int i = 0; i < lis.length; i++) {
            System.out.println(lis[i]);
        }
    }
}

​