最长上升子序列(三)

public int[] LIS (int[] arr) {
    // write code here
    int len=arr.length ,index=0;
    int[] arr1=new int[len] ,arr2=new int[len];
    for(int i=0;i<arr.length;i++){
        // 1、大数往后追加
        if(i==0 || arr[i]>arr1[index-1]){
            arr1[index++]=arr[i];
            arr2[i]=index;
        }else{// 2、非最大值寻找其大于等于值的位置进行替换并记录其为第几大
            int p1=0 ,p2=index-1;
            while(p1<p2){
                int mid=(p1+p2)/2;
                if(arr[i]>arr1[mid]){
                    p1=mid+1;
                }else{
                    p2=mid;
                }
            }
            arr1[p1]=arr[i];
            arr2[i]=p1+1;
        }
    }
    int[] res=new int[index];
    for(int i=len-1;i>=0;i--){
        // 3、遍历数组中数为第几大并取出
        if(arr2[i]==index){
            res[--index]=arr[i];
        }
    }
    return res;
}

 public class Solution {
    public int[] LIS (int[] arr) {
        // 以arr[i]结尾的最长上升子序列为dp[i]
        LinkedList<LinkedList<Integer>>[] dp = new LinkedList[arr.length];
        for (int i = 0; i < arr.length; i++) {
            dp[i] = new LinkedList<LinkedList<Integer>>();
            dp[i].add(new LinkedList<Integer>());
            dp[i].get(0).addLast(arr[i]);
            // 分别看看i是否可以加入到dp[j]的末尾
            for (int j = 0; j < i; j++) {
                // 需要严格大于才可以加入
                if (arr[i] > arr[j]) {
                    // 需要把dp[j]的全部加入到dp[i]的前面
                    for (int k = 0; k < dp[j].size(); k++) {
                        LinkedList<Integer> t = new LinkedList<Integer>(dp[j].get(k));
                        t.addLast(arr[i]);
                        dp[i].add(t);
                    }
                }
            }
        }
        return lis(dp);
    }
    private int[] lis(LinkedList<LinkedList<Integer>>[] dp) {
        LinkedList<Integer> ans = dp[0].get(0);
        for (int i = 1; i < dp.length; i++) {
            for (int k = 0; k < dp[i].size(); k++) {
                LinkedList<Integer> d = dp[i].get(k);
                if (ans.size() > d.size()) {
                    continue;
                }
                if (ans.size() < d.size()) {
                    ans = d;
                    continue;
                }
                for (int j = 0; j < ans.size(); j++) {
                    if (ans.get(j) == d.get(j)) {
                        continue;
                    } else if (ans.get(j) > d.get(j)) {
                        ans = d;
                        break;
                    }
                }
            }
        }
        return toArray(ans);
    }
    private int[] toArray(LinkedList<Integer> ans) {
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }
}

    public int[] LIS(int[] arr) {
        int n = arr.length;
        // 存放长度为length的子序列中的末位最小值
        int[] dp = new int[n + 1];
        // 辅助数组，存放以i结尾的最大长度，通过倒序遍历能够输出最小字典序的组合
        int[] p = new int[n + 1];
        // 记录当前最长子序列的长度
        int length = 1;
        dp[length] = arr[0];
        p[0] = 1;
        for (int i = 1; i < n; i++) {
            // 当前元素大于最长子序列的最后一个元素
            if (arr[i] > dp[length]) {
                length++;
                dp[length] = arr[i];
                p[i] = length;
            } else {
                // 贪心：对于一个序列，如果想让上升子序列尽量的长，那么需要让序列上升的尽可能的慢，因为需要每次在上升子序列末尾添加的数字尽可能小。
                // 举例说明：如对序列3,4,6,5。构建长度为3的上升子序列时，应该选择3,4,5而不是3,4,6。
                // 需要将dp[3](长度等于3)中记录的6 替换为5
                // 同时更新p[3](i=3)的长度为最长长度3
                // 二分查找找到恰好合适的位置（左边界）
                // 找到最左边第一个比arr[i]大的位置，然后替换。
                int left = 1;
                int right = length;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (dp[mid] < arr[i])
                        left = mid + 1;
                    else
                        right = mid;
                }
                dp[left] = arr[i];
                p[i] = left; // 长度为left，dp中的下标都代表长度
            }
        }
        int[] res = new int[length];
        for (int i = n - 1; i >= 0; i--) {
            if (p[i] == length)
                res[--length] = arr[i];
        }
        return res;
    }

最长上升子序列(贪心+二分查找 nlogn)

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组d[i]，表示长度为i的最长上升子序列的末尾元素的最小值，用len记录目前最长上升子序列的长度，起始时len为1，d[1]=nums[0]。

d[i]是关于i单增的。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = 1, n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] d = new int[n + 1];
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
}

拓展

对于现在这个d数组，如果我们想像O(n2)的解法那样维护一个 以某个下标i的元素nums[i]为结尾的子序列的长度 数组p[n]，该怎么做？

分类讨论：当前数组元素大小v对于d[len]，说明v最大，那么p[i]=len+1,其中len表示的解释最长严格递增自序列的长度。

当nums[i]==d[len]，此时p[i]取当前len值。

而当在使用二分法的情况下，当前元素v替代了第几个元素，那么就说明以v为结尾的最长严格递增子序列的长度为几。这里是pos+1。

最大上升子序列(三)(困难)

解法一（O(n2) 超时）

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        int n=arr.length;
        if(n==0) return new int[0];
        int[]dp=new int[n];
        Arrays.fill(dp,1);
        int max=1;
        int index=0;
        for(int i=1;i<n;i++){
            int  v=arr[i];
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]) dp[i]=Math.max(dp[i],dp[j]+1);
                if(dp[i]>=max){
                    index=i;
                    max=dp[i];
                }
            }
        }
        int[]res=new int[max];
        for(int i=index,j=max;j>0;i--){
            if(dp[i]==j){
                res[--j]=arr[i];
            }
        }
        return res;
    }
}

解法二 （O(nlogn)）

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
     int n=arr.length;
       int[]d=new int[n+1];
        int[]p=new int[n];
        int len=1;
       if(n==0) return new int[0];
       d[1]=arr[0];
        p[0]=1;
       for(int i=1;i<n;i++){
           int v=arr[i];
           if(v>d[len]){
           d[++len]=v;
            p[i]=len;
           }else if(v==d[len]){
              p[i]=len;
           }else{
               int l=1,r=len,pos=0;//l取1，而对于极端情况则由pos=1来弥补。
               //1 极端小时 ，pos=0 ,pos+1=1;
               //2 极端大时 ，pos=r-1, pos+1=r=len
            while(l<=r){
                int mid=(l+r)/2;
                if(d[mid]<v){
                    pos=mid;
                    l=mid+1;
                }else if(d[mid]==v){
                    r=mid-1;
                }else{
                    r=mid-1;
                }
            }
              d[pos+1]=v;
              p[i]=pos+1;
           }
       }

        int[]res=new int[len];
       for(int i=n-1,j=len;j>0;i--){
        if(p[i]==j){
            res[--j]=arr[i];
        }
       }
        return res;
    }
}

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

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();

public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        int n  = arr.length;
        int[] tail = new int[n + 1];
        // tail[i]是个辅助数组，tail[i]存储LIS长度为i的最小结尾数字
        tail[0] = Integer.MIN_VALUE;
        int end = 0;
        //dp[i]表示以arr[i]结尾的最长递增子序列长度
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            int num = arr[i];
            if (num > tail[end]) {
                end++;
                tail[end] = num; 
                dp[i] = end;
            } else {
                // 在tail中找第一个大于num的数字
                int left = 1; int right = end;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (tail[mid] < num) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                tail[left] = num;
                // dp[i]表示i位置最长序列
                dp[i] = left;
                
            }
            
        }
        //System.out.println(Arrays.toString(dp));
        // 字典序最小:若dp[i] = dp[j], i < j 那么一定有arr[j] < arr[i]
        int[] res = new int[end];
        int len = end;
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] == len) {
                res[len - 1] = arr[i];
                len--;
            }
        }
        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==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;
    }
}

import java.util.*;
public class Solution{
    public int[] LIS(int[] arr) {
        //存储最长递增序列能够有多长
        int max=Integer.MIN_VALUE;
        //空的话
        if (arr.length == 0) return arr;
        //ArrayList用于排列位置，以供howLong数组生成数据，可以称之为 howLong数组的 “工具人
        ArrayList<Integer> sort=new ArrayList<>();
        int[] howlong=new int[arr.length];
        //          遍历arr中的值，在sort 中 找到第一个大于等于 此项  的值，若找得到就把它替换了，
//          若找不到就在sort最后一项后添加上，之后返回此项的下标+1给howLong的对应arr此项的项，
//          最后与 max 比较，若它大于max，就把它的值赋给max。
        for(int i=0;i<arr.length;i++)
        {
            int flag=0;//一个标志位，表示是否能在sort中找到第一个大于等于此值的项。
            for(int j=0;j<sort.size();j++)//注意为sort.size()
            {
                if(sort.get(j)>=arr[i])
                {
                    sort.set(j,arr[i]);
                    flag=1;
                    howlong[i]=j+1;
                    break;
                }
                
            }
            
            if(flag==0)
                {
                    sort.add(arr[i]);
                    howlong[i]=sort.size();//注意这个条件
                }
                max=(max>howlong[i])?max:howlong[i];
        }
           //这个方法超时了，但是思路很清晰
//         for(int i=0;i<arr.length;i++)howLong[i]=1;
//         for(int i=1;i<arr.length;i++)
//         {
//             for(int j=0;j<i;j++)
//             {
//                 if(arr[i]>arr[j])
//                 {
//                     howLong[i]=Math.max(howLong[j]+1,howLong[j]);
//                 }
//             }
//             bigest=Math.max(bigest,howLong[i]);
            
//         }
        //创建一个 res 数组，用于返回结果，此数组的大小为max的值，因为max的值为howLong中的最大值。
       int[] res=new int[max];
        //因为在sort中每次被覆盖的值，都是比覆盖的值 大 的值，所以说【按照字典序排列】的话，就需要用到相对位置的最小值，
        //所以最后一次覆盖的值才会是最小的，故最后要从arr的尾部遍历，以保证是按字典序排列的。
        for(int i=arr.length-1,j=max;i>=0&&j>0;i-- )
        {
            if(howlong[i]==j)
            {
                res[j-1]=arr[i];
                j--;
            }
        }
        return res;
    }
}

import java.util.*;
/*
思路：
第一种动规：o（n2） 是用数组记录以当前位置为重点的子序列长度；
重点介绍
第二种优化：o(nlogn) : 另起一个数组记录子序列的末尾元素，是一个有序数组，用来辅助查找子序列长度
*/

public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        if (arr == null || arr.length <= 1) {
            return arr;
        }
        int[] subMaxNum = new int[arr.length]; // 记录长度为l的子序列最大值（末尾值） 
                                               // 用于优化dp，便于获得当前节点结尾的子序列长度
        int[] subMaxLen = new int[arr.length]; // 记录以当前位置元素结尾的子序列长度（用来追溯子序列节点）
        int maxlen = 1;
        
        subMaxNum[1] = arr[0];
        subMaxLen[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            //当当前元素大于最长子序列的末尾元素时，
            if (arr[i] > subMaxNum[maxlen]) {
                //最长子序列长度+1
                subMaxNum[++maxlen] = arr[i];
                //当前元素结尾的序列长度为maxlen
                subMaxLen[i] = maxlen;
            } else if (arr[i] < subMaxNum[maxlen]) {
                //从小到大找寻子序列中末尾元素大于当前元素的子序列长度，更新两个状态数组
                int len = findFirstBigNum(subMaxNum, arr[i], maxlen);
                subMaxNum[len] = arr[i];
                subMaxLen[i] = len;
            }
        }
        int[] res = new int[maxlen];
        for (int i = subMaxLen.length - 1; i >=0; i--) {
            if (subMaxLen[i] == maxlen) {
                res[--maxlen] = arr[i];
            }
        }
        return res;
    }
    public int findFirstBigNum(int[] arr, int pivot, int maxlen) {
        int left = 1;
        int right = maxlen;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (pivot < arr[mid]) {
                right = mid - 1;
            }
            if (pivot >= arr[mid]) {
                left = mid + 1;
            }
        }
        return left;
    }
}

二分法，end数组记录的是arr的每个数字对应的最长递增序列长度，dp数组下标i对应的是最长序列长度len(即i==len)，下标i的值对应的是以该字符结尾的最长递增子序列的结尾为dp[i],注意这里dp的理解，可以参考左神的《程序员代码面试指南数据结构题目最优解》第二版

 public static int[] LIS(int[] arr) {
        // write code here
        int[] end = new int[arr.length];
        int[] dp = new int[arr.length];
        end[0]=1;
        int len=0;
        for (int i = 0; i < arr.length; i++) {
            int left = binarySearchInsertPosition(dp, len, arr[i]);
            dp[left] = arr[i];
            if(left==len){
               len++;
            }
           end[i]=left;
        }
        len=len-1;
        int res[]=new int[len+1];
        for (int i = arr.length-1; i >=0 ; i--) {
            if(end[i]==len){
                res[len--] = arr[i];
            }
        }
        return res;
    }

    private static int binarySearchInsertPosition(int arr[], int len, int val) {
        int low = 0, high = len - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == val) {
                return mid;
            } else if (arr[mid] > val) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }