最长上升子序列(三)

    vector<int> LIS(vector<int>& arr) {
        vector<int> dp(arr.size(), 1);
        vector<int> pp(arr.size(), 0);
        int maxs = 0, maxi = 0;
        for(int i = 1; i < arr.size(); i++) {
            int lmax = 1;
            pp[i] = i; // to self
            for(int k = i-1; k >= 0; k--) {
                if(arr[i] > arr[k] && (lmax < dp[k]+1 || 
                                      (lmax == dp[k]+1 && arr[k] < arr[pp[i]])) ) {
                    lmax = dp[k]+1;
                    pp[i] = k;
                } else if(k < lmax) {
                    break;
                }
            }
            dp[i] = lmax;
            if(maxs < lmax || (maxs == lmax && arr[i] < arr[maxi]) ) {
                maxs = lmax;
                maxi = i;
            }
        }
        vector<int> vres;
        for(int k = maxi; true; k = pp[k]) {
            vres.insert(vres.begin(), arr[k]);
            if(k == pp[k]) break;
        }
        return vres;
    }

vector<int> LIS(vector<int>& arr) {
        if(arr.size() < 2) return arr;
        vector<int> dp(arr.size(), 1);
        vector<int> maxEnd(1, arr[0]);
        for(int i = 1; i < arr.size(); i++) {
            if(arr[i] > maxEnd.back()) { // in inc seq
                dp[i] = maxEnd.size()+1;
                maxEnd.push_back(arr[i]);
            } else { // ai < maxEnd
                auto pos = std::lower_bound(maxEnd.begin(), maxEnd.end(), arr[i]);
                int idx = pos - maxEnd.begin();
                maxEnd[idx] = arr[i];
                dp[i] = idx + 1;
            }
        }
        int len = maxEnd.size();
        vector<int> vres(len);
        for(int i = dp.size()-1; i >= 0; --i) {
            if(dp[i] == len) {
                vres[len-1] = arr[i];
                --len;
            }
        }
        return vres;
    }

import java.util.*;

//动态规划+二分查找
public class Solution {
    
    public int[] LIS(int[] arr) {
        // write code here
        List<Integer> cur = new ArrayList<>();
        cur.add(arr[0]);
        int[]dp = new int[arr.length];
        dp[0]=1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > cur.get(cur.size() - 1)) {
                cur.add(arr[i]);
                dp[i] = cur.size();
            } else {
                dp[i] = put(cur, arr[i])+1;
            }
        }
        int[] ans = new int[cur.size()];
        int j = cur.size(); 

        //最小的那组就得这么找
        for(int i=dp.length-1;i>=0;i--){
            if(dp[i]==j){
                ans[--j] = arr[i];
            }
        }

        return ans;
    }

    public int put(List<Integer> cur, int i) {
        int l = 0, r = cur.size()-1, m = 0;
        while (l <= r) {
            m = l + (r - l) / 2;
            if (cur.get(m) < i) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        cur.set(l, i);
        return l;
    }
}

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        //贪心+二分查找 O(nlogn)
        //维护一个数组vec，里面存放的是递增子序列
        //maxLen数组里存放的是以arr[i]为结尾的递增子序列的最大长度
        //核心思想：保证vec[]中的元素是符合条件中的最小的那一个。
        
        //第一步：利用贪心+二分求最长递增子序列长度，vec里存放的元素不一定是我们最终想要的结果，
        //但是vec里最终的数组大小就是所求的最长递增子序列的长度
        vector<int>vec;
        vector<int>maxLen;
        if(arr.size()<1) return vec;
        vec.emplace_back(arr[0]);
        maxLen.emplace_back(1);
        for(int i=1;i<arr.size();i++){
            if(arr[i]>vec.back()){
                vec.emplace_back(arr[i]);
                maxLen.emplace_back(vec.size());
            }else{
                 // lower_bound(begin, end, val)包含在<algorithm>中
                // 它的作用是返回有序数组begin..end中第一个大于等于val的元素的迭代器
                int pos=lower_bound(vec.begin(), vec.end(), arr[i])-vec.begin();
                vec[pos]=arr[i];
                maxLen.emplace_back(pos+1);
            }
        }
        //第二步：填充最长递增子序列 case:输入[2,4,6,1,5]
        int i=arr.size()-1,j=vec.size();
        for(;j>0;--i){
            if(maxLen[i]==j){
                vec[--j]=arr[i];
            }
        }
        return vec;
    }
};

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==null||arr.length<=1){
            return arr;
        }
        int len = arr.length;
        int[] dp = new int[len];
        int[] tails = new int[len];
        dp[0]=1;
        tails[0]=arr[0];
        int size = 0;
        for(int i=1;i<len;++i){
            if(arr[i]>tails[size]){
                ++size;
                tails[size]=arr[i];
                dp[i]=size+1;
            }else{
                int j = binarySearch(tails,0,size,arr[i]);
                tails[j]=arr[i];
                dp[i]=j+1;
            }
        }
        
        int[] res = new int[size+1];
        for(int i = len-1,j=size;j>=0;--i){
            if(dp[i]==j+1){
                res[j--]=arr[i];
            }
        }
        return res;
    }
    
    private int binarySearch(int[] arr,int start,int end,int val){
        while(start<end){
            int mid = start+(end-start)/2;
            if(arr[mid]<val){
                start=mid+1;
            }else{
                end=mid;
            }
        }
        return arr[start]>=val?start:start+1;
    }
}

为什么我动态规划超时！
class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    //[1,2,8,6,4]
    vector<int> LIS(vector<int>& arr) {
        // write code here
        //res[i]j记录数组中0-i的子串 的 最长公公子序列路径
        //初始化为自己本身的值，
        vector<vector<int> > res;
        for(int i=0;i<arr.size();i++){
            vector<int> tmp;
            tmp.push_back(arr[i]);
            res.push_back(tmp);
        }
        //dp[i]记录数组中o-i的最长上升子序列的长度
        vector<int> dp(arr.size(),1);
        for(int i=0;i<arr.size();i++){
            vector<int> tmp;
            for(int j=0;j<i;j++){
                if(arr[j] < arr[i]){
                    vector<int> tt = res[j];
                    tt.push_back(arr[i]);
                    res[i]= tt;
                    dp[i]=max(dp[i],dp[j] +1);
                }
            }
        }
        int max=0;
        int index=0;
        for(int i=0;i<dp.size();i++){
            if(dp[i] > max){
                index=i;
                max=dp[i];
            }
        }
        vector<vector<int> > m;
        for(int i=0;i<dp.size();i++){
            if(dp[i] == max){
                m.push_back(res[i]);
            }
        }
        sort(m.begin(), m.end());
        return m[0];
        
    }
};

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
//     arr=[2,1,5,3,6,4,8,9,7]
//     dp =[1,3  ,4,  7  ,9]
//     ans=[1,13,134,1347,13489]
    
    public int[] LIS (int[] arr) {
        // write code here
        int n = arr.length;
        StringBuilder[] ans = new StringBuilder[100005];
        ans[0] = new StringBuilder("");
        int[] dp = new int[100005];//dp[i]维护的是长度为i的最后一个数字的最小值
        int size = 0;
        for(int i=0;i<n;i++){
            int l = 0,r = size;
            while(l<r){ //二分找在dp的（l,r）中比arr[i]小的最大的数的下标
                int mid = (l+r+1)/2;
                if(arr[i]>dp[mid]){
                    l = mid;
                }else{
                    r = mid-1;
                }
            }
            size = Math.max(size,r+1);
//             System.out.println("r:"+r);
            dp[r+1] = arr[i]; //更新dp的r+1的位置的值为arr[i]
            StringBuilder sb = new StringBuilder(ans[r]);
            ans[r+1] = sb.append(String.valueOf(arr[i])+" ");  //将答案更新为ans[r]+arr[i]
        }
//         System.out.println(ans[size].toString());
        String[] res = ans[size].toString().split(" ");//将答案切分转成int类型
        int[] resint = new int[res.length];
        for(int i=0;i<res.length;i++){
            resint[i] = Integer.parseInt(res[i]);
        }
        return resint;
    }
}

超时版：

function LIS( arr ) {
    if (arr === null || arr.length === 0) return 0;
    const dp = new Array(arr.length).fill(1);
    let max = 1;
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
                max = Math.max(max, dp[i]);
            }
        }
    }
    const result = new Array(max);
    for (let i = dp.length - 1; i >= 0; i--) {
        if (dp[i] === max) result[--max] = arr[i];
    }
    return result;
}

通过版：

function LIS( arr ) {
    const list = new Array(arr.length + 1);
    const maxLen = new Array(arr.length);
    let n = 1;
    list[1] = arr[0];
    maxLen[0] = 1;
    for (let i = 0; i < arr.length; i++) {
        if (list[n] < arr[i]) {
            list[++n] = arr[i];
            maxLen[i] = n;
        } else {
            const index = binarySearch(list, n, arr[i]);
            list[index] = arr[i];
            maxLen[i] = index;
        }
    }
    const result = new Array(n);
    for (let i = maxLen.length - 1; i >= 0; i--) {
        if (maxLen[i] === n) result[--n] = arr[i];
    }
    return result;
}
function binarySearch(arr, right, key) {
    let left = 0;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] >= key) right = mid - 1;
        else left = mid + 1;
    }
    return left;
}

1. 定义动态数组，int[] dp = new int[N];并全部赋初值为1，Arrays.fill(dp,1），dp代表nums 前 i 个数字的最长子序列长度
2. 定义TreeSet，一种有序队列。并将数组首位加入到set
3. 当数组元素大于set的最后末尾元素时，加入set，dp[i] = set.size()。否则就用ceiling（arr[i]）找到大于当前元素的值，并使用remove删除，并将当前元素加入set，dp[i] = set.headSet(arr[i]).size() + 1（因为可能存在连续加入set的情况，这样遇到arr[i] < set.last()时，就只能删除一个set.celling()，此时，用set.size()就不对了）
4. 定义一个res，长度是set.size();
5. 从后向前遍历，如果dp[i] == j，res[--j] = arr[i]。j表示set.size();