Bridging Signals (POJ 1631)

The problem is just a equivalent of finding the length longest increasing subsequence from given subsequences as if we only preserve the connection to endpoint numbered by items in that subseqence, there won't be a cross among every pairs of connections. Also we can not find a larger solution to this problem.

import java.io.*;
import java.util.*;

public class BridgingSingals {
    static private int[] array = new int[40010];
    static private int[] dp = new int[40010];
    static private int[] count = new int[40010];

    private static int upperbound(int[] array, int value, int len) {
        int l = 0, r = len - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (array[mid] <= value) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
    private static void solve(int p) {
        for (int i = 0; i <= p; i++) {
            count[i] = 50000;
        }
        count[0] = Integer.MIN_VALUE;
        int max = 1;
        for (int i = 0; i < p; i++) {
            int c = upperbound(count, array[i], p);
            dp[i] = Math.max(1, c + 1);
            count[dp[i]] = Math.min(count[dp[i]], array[i]);
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int p = in.nextInt();
            for (int i = 0; i < p; i++) {
                array[i] = in.nextInt();
            }
            solve(p);
        }
    }
}