NC91 最长递增子序列

二刷 贪心 + 二分 + dp 保存状态
tail 保存 长度为 i的子序列的 最小的结尾的值（贪心+二分）
dp 保存 位置为i的 最长子序列长度

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {

        int[] tail = new int[arr.length];
        int[] dp = new int[arr.length];
        tail[0] = arr[0];
        int end = 0;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > tail[end]) {
                tail[++end] = arr[i];
                dp[i] = end;
            }
            else {
                int l = 0;
                int r = end - 1;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (arr[i] > tail[mid] && arr[i] <= tail[mid + 1]) {
                        l = mid+1;
                        break;
                    } else if (arr[i] > tail[mid]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                tail[l] = arr[i];
                dp[i] = l;
            }
        }
        // 寻找最小字典序
        int [] res = new int[end+1];
        int i = arr.length-1;

        for(;i>=0 && end >=0; i--){
            if(dp[i]==end){
                res[end] = arr[i];
                end--;
            }
        }

        return res;


    }

}

动态规划
从最后一个开始选就可以 保证是最小字典序

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        if( arr.length<2){
            return arr;
        }

        int[] dp = new int[arr.length];
        dp[0] = 1;


        int maxans = 1;
        for (int i = 1; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        // 寻找最小字典序 
        int [] res = new int[maxans];
        int i = arr.length-1;

        for(;i>=0 && maxans >0; i--){
            if(dp[i]==maxans){
                res[maxans-1] = arr[i];
                maxans--;
            }
        }

        return res;
    }
}