NYOJ 214 单调递增子序列

描述
    给定一整型数列{a1,a2...,an}（0<n<=100000），找出单调递增最长子序列，并求出其长度。
    如：1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13，长度为5。
输入
    有多组测试数据（<=7）
    每组测试数据的第一行是一个整数n表示序列易做图有n个整数，随后的下一行里有n个整数，表示数列中的所有元素.每个整形数中间用空格间隔开（0<n<=100000）。
    数据以EOF结束。
    输入数据保证合法（全为int型整数）！
输出
    对于每组测试数据输出整形数列的最长递增子序列的长度，每个输出占一行。
样例输入
    7
    1 9 10 5 11 2 13
    2
    2 -1
样例输出
    5
    1

2思路：DP（最长上升子序列）
3分析：
           1dp[i]表示以第i个元素为结尾的最长的长度，tmpNum[i]表示递增子序列长度为i的最后一个值的最小值，那么就有tmpNum[1]< tmpNum[2]<......<tmpNum[k],k为最长的长度。
           2那么我们每次就可以根据当前的元素num[i]在tmpNum数组中的位置j来确定当前的dp[i]。如果当前的num[i]在tmpNum数组中最小即j = 0，那么dp[i] = 1，tmpNum[1] = num[i] ; 否则dp[i] = j； tmpNum[j] = num[i];
           3确定num[i]在tmpNum数组中的位置用STL 中的lower_bound()；返回第一个>=num[i]的迭代器。
           4样例分析：例如 2 1 2，那么首先初始化tmpNum[0] = tmpNum[1] = ..... = INF;
        num[0] = 2 ; 这个时候num[0]比tmpNum数组中的任何值都小，所以j = 1 ，那么更新后 tmpNum[0] = INF , tmpNum[1] = 2 .....
        num[1] = 1 ; 这个时候num[1]比tmpNum数组中的任何值都小，所以j = 1 ，那么更新后 tmpNum[0] = INF , tmpNum[1] = 1 ......
        num[2] = 2 ; 这个时候num[2]比tmpNum数组中tmpNum[2]小，所以j = 2 ，那么更新后 tmpNum[0] = INF , tmpNum[1] = 1 tmpNum[2] = 2.....

4代码：
[cpp]
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAXN 100010
#define INF 0xFFFFFFF

int n , ans;
int num[MAXN];
int tmpNum[MAXN];
int dp[MAXN];

void solve() {
    memset(dp , 0 , sizeof(dp)) ; ans = 0;
    for(int i = 0 ; i < n ; i++) tmpNum[i] = INF;
    for(int i = 0 ; i < n ; i++){
        int j = lower_bound(tmpNum , tmpNum+n , num[i])-tmpNum;
        if(!j) j = 1;
        dp[i] = j;
        tmpNum[j] = num[i];
        if(ans < dp[i]) ans = dp[i];
    }
    printf("%d\n" , ans);
}

int main() {
    //freopen("input.txt", "r", stdin);
    while(scanf("%d%*c" , &n) != EOF){
        for(int i = 0 ; i < n ; i++)
            scanf("%d" , &num[i]);
        solve();
    }
    return 0;
}

补充：软件开发 , C++ ,