タイトル1533:最長上昇サブシーケンス-9度

タイトルの説明:
整数配列を与え,この配列の最長厳格な増分サブシーケンスの長さを求める.例えば、シーケンス1 2 2 4 3の最長厳格増分サブシーケンスは、1,2,4または1,2,3である.彼らの長さは3です.
入力:
入力には、複数のテストケースが含まれる場合があります.各テストケースについて、入力される第1の動作の整数n(1<=n<=10000000):入力するシーケンスの長さを表す第2の行には、この配列の数値を表すn個の整数が含まれる.整数はintの範囲内です.
出力:
各テストケースについて、最長厳格なサブシーケンス長を出力します.
サンプル入力:

4
4 2 1 3
5
1 1 1 1 1

サンプル出力:

2
1

推奨指数:※※
ソース:http://ac.jobdu.com/problem.php?pid=1533
dp O(n^2)の考え方はもう述べないでください.
ここで、seqレコードを用いて、最長シーケンス長がxの場合、シーケンスの最大値は最小値(後の数に機会を残し、より大きなシーケンスを取得する可能性が高い)をとることができ、seq[x]レコードは対応する値である.
ここで余談ですが、演算子の優先度はシフト演算子より高く、括弧を付けてください.

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
using namespace std;
const int N=10001;
int pos_min(vector<int> *num,int val){
   int low=0,high=(*num).size()-1;
   while(low<=high){
       int mid=low+((high-low)>>1);
       if((*num)[mid]>=val)
           high=mid-1;
       else if((*num)[mid]<val)
           low=mid+1;
   }
   return low;
}
int max_seq(int *num,int len){
    int i;
	vector<int> seq;
    for(i=0;i<len;i++){
		int index=pos_min(&seq,num[i]);
		if(index>=seq.size())
			seq.push_back(num[i]);
		else
			seq[index]=num[i];
	}
	return seq.size();
}
int main()
{
	int n,i;
	while(scanf("%d",&n)!=EOF){
		int *num=new int [n];
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		int longest=max_seq(num,n);
		printf("%d
",longest);
	}
	return 0;
}

手順の説明:http://www.cnblogs.com/mengxm-lincf/archive/2011/07/12/2104745.html