题目链接：CODE【VS】1576 最长严格上升子序列
题目描述:
给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）
例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10。
Input
第1行：1个数N，N为序列的长度(2 <= N <= 50000)
第2 - N + 1行：每行1个数，对应序列的元素(-10^9 <= S[i] <= 10^9)
Output
输出最长递增子序列的长度。
Input示例
8
5
1
6
8
2
4
5
10
Output示例
5
方法一：
阶段：以数组中每个元素为阶段, 共n个阶段
状态：以第i个元素为结尾的最长递增子序列长度(初始化为1)
决策：第j（j < i）个元素能否与第i个元素构成递增序列
转移方程：
dp[i] = max(dp[i], dp[j]+1) (i>j)
方法二：
阶段：以数组中每个元素为阶段, 共n个阶段
状态：以第i个元素，更新，最大元素最小的，递增子序列（维护dp数组，使其中每个元素尽可能小，其长度为递增序列长度，但dp不一定是递增的）。
决策：第i个元素可以放在dp数组里的什么位置（在dp数组中寻找大于a[i]的最小的，如果没有，dp数组长度+1,a[i]至于dp末尾）
较容易证明dp数组为单调递增数组，所以在寻找dp数组中，比a[i]大的最小元素可以用利用二分法（logn），从而减少比较次数
转移方程：
dp[j] = a[i] (max dp[j] (dp[j] > a[i]) ) (i>j)
代码如下：
/***************************************************
> File Name: 单增子序列.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年02月29日 星期一 16时34分11秒
***************************************************/
#include<iostream>
#include<stdio.h>
using namespace std;
int a[50008];
int dp[50008];
int main()
{
int n;
cin>>n;
for(int i = 0; i < n; i++)
{
cin>>a[i];
}
int max = 1;
dp[0] = 1;
//方法一：复杂度：o(n^2)
for(int i = 1; i < n; i++)
{
dp[i] = 1;
for(int j = 0; j < i; j++)
{
if(a[j] < a[i] && dp[j] + 1 > dp[i])///*****
dp[i] = dp[j] + 1;
}
if(dp[i] > max) max = dp[i];
}
cout<<max<<endl;
/*
//方法二：时间复杂度o(nlogn)
int len = 1, mid;
dp[0] = a[0];
for(int i = 1; i < n; i++)
{
left = 0;
right = len;
while(left < right)
{
mid = (left + right) / 2;
if(dp[mid] < a[i]) left = mid + 1;
else right = mid;
}
dp[left] = a[i];
if(left >= len) len++;
}
cout<<len;*/
return 0;
}