http://topic.csdn.net/t/20061218/23/5239809.html

1.       先安装netbeans和c++插件

2.       找到cygwin，选择devel下的（视频教程里少了最后两项，按视频教程那样安装再加上最后两项就ok了）

gcc 核心(c编译器)              3.4.x

gcc-c++(c++编译器)     3.4.x

gdb(GUN调试器)          6.5.50

make                             3.80

3.       完后把cygwin目录下的bin文件以及usr里的bin(or sbin)放到环境变量path里去

例如：D:\cygwin\bin; D:\cygwin\usr\sbin

　　对于一个序列a[0]...a[n]，设F[i]表示到第i个数为止的最大上升子序列，我们考虑如这种情况，存
在0<=y<x<i=n，若满足

(1) y<x<i;

(2) a[x]<a[y]<a[i]; 

(3) |F[x]| == |F[y]|;

 (4) a[j] < a[x], y < j < x

　　则此时F[i]应该由F[x]扩展而来，因为可能存在z满足

(1) y<x<z<i; 

(2) a[x]<a[z]<a[y]<a[i]

(3) z < min{j | a[j]>a[y], j > x}

　　则此时用F[x]扩展得到F[i]将长于F[y]扩展得到的子序列。 由此可得出结论，原序列第i个元素之前最长
子序列的解可能存在很多，但我们只需要尽可能使得那个最长子序列的最后一个元素的值最小，就能向后扩展得
到原串最长子序列。

　　求解的过程依然是一个动态规划的过程，我们采用一个数组d[k]，来描述到状态i时长度为k的子序列最后一
个元素的最小值。从状态i-1转移到状态i时，a[i]的加入影响到数组中的d[k]，k满足

k = max{a[i]>d[j]} + 1

此时有

d[k] = min{d[k], a[i]}

　　由此我们会发现数组d一个明显的特征，即d是一个单调上升的序列，利用这个特性，我们可以采用二分法来
查找k的值，这样使得整体的时间复杂度从原来的n2变为nlog2n，但是在设计过程中应该要注意到数组d的首元素
和尾元素的处理。最后，我们所需要的值就是在末状态时d数组的最大下标值，这里值得注意的是数组d的下表的
最大值应该是在变化的——反观定义则可明显地得到这个特性。

　　一下是一段源代码，测试过一个小数据，设计中发现整个算法的难点在于二分法查找的设计。
*/

#include <cstdio>
#include <cstdlib>
#include <climits>
#include <iostream>
using namespace std;
#define MAX 1000
int a[MAX];
int d[MAX];
int max_subsequence (const int size )
{
    int n;
    d[ n = 0 ] = a[ 0 ];
    for ( int i = 1; i < size; i++ )
        if ( d[ n ] < a[ i ] )
            d[ ++n ] = a[ i ];
        else if ( d[ 0 ] > a[ i ] )
            d[ 0 ] = a[ i ];
        else
        {
            int left = 0, right = n, mid = n / 2, key = a[ i ];
            while ( left < right ){
                if ( d[ mid ] == key )
                {
                    mid--;
                    break;
                }
                if ( d[ mid ] > key )
                {
                    right = mid;
                    mid = ( left + right ) / 2;
                }
                else if ( mid > left )
                {
                    left = mid;
                    mid = ( left + right ) / 2;
                }
                else
                    break;
            }
            if ( d[ mid + 1 ] > key )
                d[ mid + 1 ] = key;
        
        }
    return n + 1;
}

int main ( )
{
    int n;
    scanf ( "%d", &n );
    for ( int i = 0; i < n; i++ )
        scanf ( "%d", &a[ i ] );
    printf ( "%d\n", max_subsequence ( n ) );
  //  system ( "pause" );
 return 0;
}