最长上升子序列(三)

    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;
    }

public class Solution {
    public int[] LIS (int[] arr) {
        int n = arr.length;
        if (n == 0)    //特判空情况，方便后面处理
            return new int[0];
        
        int[] ls = new int[n];    //注意不能用list，会超时。所以直接开一个大数组，动态扩张
        int[] dp = new int[n];
        
        int l = 1;    //ls递增序列的实际长度
        ls[0] = arr[0];
        dp[0] = 1;
        
        for (int i = 1; i < n; i++) {
            if (ls[l - 1] < arr[i]) {
                ls[l++] = arr[i];    //直接加入序列
                dp[i] = l;    //dp[i]对应的序列是整个ls
            }
            else {
                int j = 0, k = l - 1;
                int ind = 0;
                //找ls中第一个 >= arr[i]的（必定存在，因为保证ls的最后一个 >= arr[i]）
                while (j <= k) {
                    int m = j + (k - j) / 2;
                    if (ls[m] >= arr[i]) {
                        ind = m;
                        k = m - 1;
                    }
                    else {
                        j = m + 1;
                    }
                }
                ls[ind] = arr[i];    //找到位置后替换掉，注意是替换不是插入
                //ls序列的总长不变，但是为了复用原序列一些 < arr[i]的结果，选择二分把arr[i]替换到合适的位置
                //所以dp[i]对应的序列其实是ls的[0, ind]部分（要保证序列的最后是arr[i]），即长度为ind + 1
                dp[i] = ind + 1;
            }
        }
        
        //这里其实可以复用ls来填充的，但是用ans是为了说明求最后的子序列和ls无关
        //ls只是为了上面求dp的复杂度从O(n ^ 2)降低为O(n * logn)
        //这里的求法是倒着遍历，找到满足长度的dp就记录，然后更新。（即同样值的dp，选尽量靠右边的）
        int[] ans = new int[l];
        for (int i = n - 1, j = l; i >= 0; i--) {
            if (dp[i] == j) {
                ans[--j]  = arr[i];
            }
        }
        
        return ans;
    }
}

    public int[] LIS (int[] temp) {
        int N = temp.length;
        int[] dp = new int[N];
        Arrays.fill(dp, 1);
        TreeSet<Integer> set = new TreeSet<>();
        set.add(temp[0]);
        for(int i = 1; i < dp.length; i++) {
            if(temp[i] > set.last()) {
                set.add(temp[i]);
                dp[i] = set.size();
            } else {
                int first = set.ceiling(temp[i]);
                set.remove(first);
                set.add(temp[i]);
                dp[i] = set.headSet(temp[i]).size() + 1;
            }
        }
        int[] res = new int[set.size()];
        for(int i = temp.length - 1, j = set.size(); i >= 0; i--) {
            if(dp[i] == j) {
                res[--j] = temp[i];
            }
        }
        return res;
    }

import java.util.*;
public class Solution {
    public int[] LIS (int[] arr) {
        if(arr == null || arr.length <= 0){
            return null;
        }

        int len = arr.length;
        int[] count = new int[len];             // 存长度
        int[] end = new int[len];               // 存最长递增子序列

        //init
        int index = 0;                          // end 数组下标
        end[index] = arr[0];
        count[0] = 1;

        for(int i = 0; i < len; i++){
            if(end[index] < arr[i]){
                end[++index] = arr[i];
                count[i] = index;
            }
            else{
                int left = 0, right = index;
                while(left <= right){
                    int mid = (left + right) >> 1;
                    if(end[mid] >= arr[i]){
                        right = mid - 1;
                    }
                    else{
                        left = mid + 1;
                    }
                }
                end[left] = arr[i];
                count[i] = left;
            }
        }

        //因为返回的数组要求是字典序，所以从后向前遍历
        int[] res = new int[index + 1];
        for(int i = len - 1; i >= 0; i--){
            if(count[i] == index){
                res[index--] = arr[i];
            }
        }
        return res;
    }
}

import java.util.*;

/**
 * 问题可以转化为求该序列和已排好序的序列的最长公共子序列
 * 用动态规划轻松搞定
 * 注意字典序，需要反向比较
 * 需要设置标志位，以便后面打印输出
 */

public class Solution {
    int[] res;
    int index = 0;

    public int[] LIS (int[] arr) {
        if(arr == null || arr.length <= 0){
            return res;
        }
        reverse(arr);
        int[] nums = arr.clone();
        Arrays.sort(nums);
        reverse(nums);

        int n = arr.length;
        int[][] flags = new int[n + 1][n + 1];//用于打印输出

        int len = LCS(nums,arr, flags, n);

        res = new int[len];
        helper(nums, flags, res, n, n);

        reverse(res);
        return res;
    }

    //找到最大长度，并标记（方便存储打印）
    public int LCS(int[] nums1, int[] nums2, int[][] flags, int n){
        int[][] dp = new int[n + 1][n + 1];//记录最大长度
        for(int[] a : dp){
            Arrays.fill(a, 0);
        }
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    flags[i][j] = 1;                    //相等设置为 1
                }
                else if(dp[i - 1][j] > dp[i][j - 1]){
                    dp[i][j] = dp[i - 1][j];               //选大的
                    flags[i][j] = 2;
                }
                else{
                    dp[i][j] = dp[i][j - 1];
                    flags[i][j] = 3;
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }

    //存起来
    public void helper(int[] nums,int[][] flags, int[] res,  int i, int j){
        if(i == 0 || j == 0){
            return;
        }
        if(flags[i][j] == 1){
            helper(nums, flags, res, i - 1, j - 1);
            res[index++] = nums[i - 1];
//            System.out.print(nums[i - 1] + " ");
        }
        else if(flags[i][j] == 2){
            helper(nums, flags, res, i - 1, j);
        }
        else{
            helper(nums, flags, res, i, j - 1);
        }
    }

    public void reverse(int[] nums){
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            swap(nums, left, right);
            left ++;
            right--;
        }
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

# l[i]记录以A[i]结束的最长递增子序列的长度
# res为最长递增子序列，当存在两个或以上的序列时，返回字典序最小的那个
import bisect
class Solution:
    def LIS(self , A ):
        # write code here
        d = []
        c = 0
        l = []
        for a in A:
            i = bisect.bisect_left(d, a)  # 二分
            if i < len(d):
                l.append(l[A.index(d[i])])
                d[i] = a
            elif not d or d[-1] < a:
                d.append(a)
                c += 1
                l.append(c)
        print(l)
        print(d)  # 此时最长递增子序列的长度已求出，即为len(d)，但没求出最长递增子序列本身的样子
        res = [A[l.index(max(l))]]
        tmp = max(l) - 1
        for i in range(l.index(max(l)) - 1, -1, -1):
            if tmp == 1 and l[i] == tmp:
                res.append(A[i])
                break
            if l[i] == tmp:
                res.append(A[i])
                tmp -= 1
        res.reverse()
        return res

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        int n = arr.size();
        vector<int> q(n + 1);
        vector<int> f(n + 1);
        int len = 0;
        q[0] = -2e9;
        for (int i = 0; i < n; ++i) {
            int l = 0, r = len;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] < arr[i]) l = mid;
                else r = mid - 1;
            }
            f[i] = r + 1;  // 记录以第 i 个元素结尾的最长上升子序列的长度
            len = max(len, r + 1);
            q[r + 1] = arr[i];
        }
        vector<int> res(len);
        for (int i = f.size() - 1; i >= 0; --i) {
            if (f[i] == len) {
                res[len - 1] = arr[i];
                --len;
            }
        }
        return res;
    }
};

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        vector<vector<int>> dp;
        dp.push_back({INT_MIN});//dp[0]={INT_MIN}
        //初始状态dp[0]={INT_MIN}，因为dp[1]长度为1字典序最小的递增子序列可能需要更新
        if (arr.empty()) return dp[0];
        dp.push_back({ arr[0] });
        for (int i = 1; i<arr.size(); i++)
        {        
            for (int len = dp.size(); len >= 0; len--)
            {
                //遍历dp从dp[len-1]开始遍历
                int tmp = dp[len-1].back();
                if (arr[i]>tmp&&len == dp.size())
                {//dp长度也就是递增子序列长度增加，新建 dp[j+1]=dp[j]+{arr[i]}
                    vector<int> dp_i = dp.back();
                    dp_i.push_back(arr[i]);
                    dp.push_back(dp_i);
                    break;
                }
                else if (arr[i]>tmp&&len<dp.size())
                {//向前遍历dp[len-1].back 找到arr[i] >dp[len-1].back()后，更新dp[len]=dp[len-1]+{arr[i]}
                    if (len == 1) dp[len].pop_back();
                    else dp[len] = dp[len - 1];
                    dp[len].push_back(arr[i]);
                    break;
                }
                
            }
        }
        return dp.back();
    }
};