题解 | #最长递增子序列#

dp + 二分查找， 记录序列

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    class Num {
        int n;
        int i;
        public Num(int n, int i) {
            this.n = n;
            this.i = i;
        }
    }
    public int[] LIS (int[] arr) {
        int dp[] = new int[arr.length+1];
        int count = 1;
        dp[1] = arr[0];
        Map<Integer, ArrayList<Num>> m = new HashMap<Integer, ArrayList<Num>>();
        ArrayList<Num> e = new ArrayList<>();
        e.add(new Num(arr[0], 0));
        m.put(1, e);

        for (int i = 1; i < arr.length; i++) {
            int left = 1;
            int right = count;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arr[i] < dp[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            if (right == 0) {
                dp[1] = arr[i];
                m.get(1).add(new Num(arr[i], i));
            } else if (left == count + 1) {
                if (arr[i] == dp[count]) {
                    m.get(count).add(new Num(arr[i], i));
                    continue;
                }
                count++;
                dp[count] = arr[i];

                ArrayList<Num> e1 = new ArrayList<>();
                e1.add(new Num(arr[i], i));

                m.put(count, e1);
            } else {
                dp[left] = arr[i];
                m.get(left).add(new Num(arr[i], i));
            }
        }
        traval(m, count, 0, dp);
        int[] result = new int[count];
        for (int i = 1; i <= count; i++) {
            result[i-1] = dp[i];
        }
        return result;
    }

    public void traval(Map<Integer, ArrayList<Num>> m, int count, int index, int[] dp) {
        if (count == 0) {
            return;
        }

        int minV = Integer.MAX_VALUE;
        int minI = 0;
        if (index == 0) {
            for (Num x: m.get(count)) {
//                 System.out.println(count+"=>"+x.n);
                if (x.n < minV) {
                    minV = x.n;
                    minI = x.i;
                } else if (x.n == minV && x.i > minI) {
                    minI = x.i;
                }
            }
            dp[count] = minV;
            traval(m, count -1, minI, dp);
        } else {
            for (Num x: m.get(count)) {
//                 System.out.println(count+"=>"+x.n);
                if (x.i < index && x.n < minV) {
                    minV = x.n;
                    minI = x.i;
                } else if (x.i < index && x.n == minV && x.i > minI) {
                    minI = x.i;
                }
            }
            dp[count] = minV;
            traval(m, count - 1, minI, dp);
        }
    }
}