BOJ. Longest Increasing Subsequence(4) (14002)

Problem link

For each input value, maintain tails[length], the smallest possible ending value of an increasing subsequence of that length, along with the input index that supplies that tail. Binary-search for the first tail greater than or equal to the current value (lower_bound) and replace it. Tails are minimal endpoints, not necessarily a subsequence themselves; their indices are kept so we can recover a real subsequence.

Using the first tail >= value is what makes the subsequence strictly increasing: a value equal to an existing tail replaces it instead of extending the sequence. The predecessor of the current index is the index stored for the preceding length before updating the tails. Following those predecessor links from the final longest tail yields the chosen subsequence in reverse; reversing it gives the answer.

The binary search and update take O(log N) per value, so the total time complexity is O(N log N). The input, tails, tail indices, predecessor links, and reconstructed answer each use O(N) space. A singleton produces a sequence of length one; repeated or decreasing values never incorrectly extend the subsequence.

import java.io.*;

public class Main {
    private static final class FastScanner {
        private final InputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int length;
        private int position;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) return -1;
            }
            return buffer[position++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value * sign;
        }
    }

    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        int[] values = new int[n];
        int[] tails = new int[n];
        int[] tailIndices = new int[n];
        int[] predecessor = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = input.nextInt();
            predecessor[i] = -1;
        }

        int length = 0;
        for (int i = 0; i < n; i++) {
            int value = values[i];
            int left = 0;
            int right = length;
            while (left < right) {
                int middle = left + (right - left) / 2;
                if (tails[middle] >= value) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }

            int position = left;
            if (position > 0) predecessor[i] = tailIndices[position - 1];
            tails[position] = value;
            tailIndices[position] = i;
            if (position == length) length++;
        }

        int[] answer = new int[length];
        int index = tailIndices[length - 1];
        for (int i = length - 1; i >= 0; i--) {
            answer[i] = values[index];
            index = predecessor[index];
        }

        StringBuilder output = new StringBuilder();
        output.append(length).append('\n');
        for (int value : answer) output.append(value).append(' ');
        System.out.println(output);
    }
}