SEERC 2008 Problem A Stock Exchange

POJ 3903

题目大意

给定一个数组P，寻找最长的递增子序列，数组最大长度100000。

解决方案

很经典的问题了，由于数据比较庞大，需要Nlog(N)的算法 ​​​​​​​

Example

需要测试数据的同学可以留言

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) {
        new Main().run();
    }

    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    private int readInt() {
        int r;
        try {
            int t;
            while (true) {
                t = reader.read();
                if (t == -1) return -1;
                if (Character.isDigit(t)) {
                    r = t - '0';
                    while (true) {
                        t = reader.read();
                        if (!Character.isDigit(t)) {
                            break;
                        }
                        r = r * 10 + (t - '0');
                    }
                    break;
                }
            }
        } catch (Exception e) {
            return -1;
        }
        return r;
    }

    int n;
    int[] p = new int[100000];

    private int binarySearch(int toIndex, int key) {
        int low = 0;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = p[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

    private void run() {
        while ((n = readInt()) > 0) {
            for (int i = 0; i < n; i++) {
                p[i] = readInt();
            }
            int tail = 1;

            for (int i = 1; i < n; i++) {
                if (p[i] > p[tail - 1]) {
                    p[tail++] = p[i];
                } else {
                    int where = binarySearch(tail, p[i]);

                    if (where < 0) {
                        p[-(where + 1)] = p[i];
                    }
                }
            }
            System.out.println(tail);
        }
    }
}