LIS-最长上升子序列

例 ：
给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:
输入: [10,9,**2,5,3,7,101**,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
**

递推实现

dp[i] = max(dp[i],dp[j]+1)
**

import java.util.Scanner;
public class LIS {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0;i<n;i++) {
            a[i] = sc.nextInt();
        }
        int[] dp = new int[a.length];
        int res = 0;
        for (int i = 0; i < a.length; i++) {
            dp[i] = 1;
            for (int j = 0; j <= i; j++) {
                if (a[j] < a[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        System.out.println(res);
    }
}

堆栈实现

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {

    static int L, top;
    static long D[];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        while (st.nextToken() != StreamTokenizer.TT_EOF) {
            // input read
            L = (int) st.nval;
            D = new long[L];
            top = 0;
            for (int i = 0; i < L; i++) {
                st.nextToken();
                long cur = (long) st.nval;

                // first
                if (top == 0) {
                    D[top++] = cur;
                    continue;
                }

                // same
                if (cur == D[top - 1])
                    continue;

                // bigger ,add
                if (cur > D[top - 1])
                    D[top++] = cur;
                else {
                    int idx = Arrays.binarySearch(D, 0, top, cur); // find
                    idx = idx < 0 ? -idx - 1 : idx;
                    D[idx] = cur; // replace
                }
            }
            System.out.println(top);
        }
    }
}

索引树实现

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {

    static int L, T_IDX;
    static Stock D[];
    static long IT[];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        while (st.nextToken() != StreamTokenizer.TT_EOF) {
            // input read
            L = (int) st.nval;
            D = new Stock[L];
            for (int i = 0; i < L; i++) {
                st.nextToken();
                D[i] = new Stock(i, (long) st.nval);
            }
            // cal tree index
            T_IDX = 1;
            while (T_IDX < L) {
                T_IDX = T_IDX + T_IDX;
            }
            // init indexed tree
            IT = new long[2 * T_IDX];
            Arrays.sort(D);

            // main
            for (int i = 0; i < L; i++) {
                long cur_val = query(T_IDX, T_IDX + D[i].idx - 1) + 1;
                update(T_IDX + D[i].idx, cur_val);
            }
            // out
            System.out.println(IT[1]);
        }
    }

    static long query(int s, int e) {
        long rst = 0;
        while (s <= e) {
            if (s % 2 == 1)
                rst = Math.max(rst, IT[s]);

            if (e % 2 == 0)
                rst = Math.max(rst, IT[e]);

            s = (s + 1) >> 1;
            e = (e - 1) >> 1;
        }
        return rst;
    }

    static void update(int x, long val) {
        while (x > 0 && IT[x] < val) {
            IT[x] = val;
            x = x >> 1;
        }
    }

    static class Stock implements Comparable<Stock> {
        int idx;
        long val;

        public Stock(int idx, long val) {
            super();
            this.idx = idx;
            this.val = val;
        }

        public int compareTo(Stock that) {
            if (this.val == that.val)
                return that.idx - this.idx;
            return this.val - that.val;
        }

    }
}