Java程序练习-bridging signals----最长升序列

bridging signals----最长升序列
时间限制: 10000ms内存限制: 10240kB
描述
有一个二分图的完全匹配，二分图两个顶点集合大小相等。现在要从中取定尽量多的边，使得任意两条边都不相交。如下图所示，连接关系是(4, 2, 6, 3, 1, 5)，最多取3条边，满足要求。
输入
第一行是整数p，p<40000，表示每个集合顶点个数。
接下来的p行，每行一个数，依次表示左边的点与哪一个右边的点连接。
输出
一个整数，表示做多的边数
样例输入
6
4
2
6
3
1
5
样例输出
3
参考代码
view plainprint?
/*
* Title :bridging signals
* From   :http://nnsznoi.openjudge.cn/lst/18/
* Time   :2011-10-11 19:58PM
* Author :Eric Zhou,binfeihan
* Email :binfeihan@126.com
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(cin.readLine().trim());
        int i,j,len,v[] = new int[n];
        int dp[] = new int[n];
        for(i = 0;i < n;++ i)
            v[i] = Integer.parseInt(cin.readLine().trim());
        dp[1] = v[0];
        len = 1;
        for(i = 1;i < n;++ i){
            j = bsearch(dp,len,v[i]);
            dp[j] = v[i];
            if(j > len)
                len = j;
        }
        System.out.println(len);
    }
    private static int bsearch(int[] arr, int len, int n) {
         int left = 0,right = len,mid = (left + right) / 2;
         while(left <= right){
             if(n > arr[mid])
                 left = mid + 1;
             else if(n < arr[mid])
                 right = mid - 1;
             else
                 return mid;
             mid = (left + right) / 2;
         }
         return left;
    }
}

摘自：冰非寒

补充：软件开发 , Java ,