九度OJ 1533 最长上升子序列 -- 动态规划 - c++编程基础

题目描述：

给定一个整型数组，求这个数组的最长严格递增子序列的长度。譬如序列1 2 2 4 3 的最长严格递增子序列为1，2，4或1，2，3.他们的长度为3。

输入：

输入可能包含多个测试案例。
对于每个测试案例，输入的第一行为一个整数n(1<=n<=100000)：代表将要输入的序列长度
输入的第二行包括n个整数，代表这个数组中的数字。整数均在int范围内。

输出：

对于每个测试案例，输出其最长严格递增子序列长度。

样例输入：

样例输出：

2
1

参考《编程之美》2.16

对于前面i个元素的任何一个递增子序列，如果这个子序列的最大的元素比array[i+1]小，那么就可以将array[i+1]加在这个子序列后面，构成一个新的子序列。

比如当i=4的时候，目标序列为：1,-1,2,-3,4,-5,6,-7最长递增序列为：(1, 2),(-1, 2)。那么，只要4>2，就可以把4直接增加到前面的子序列中形成一个新的递增子序列。

因此，我们希望找到前i个元素的一个递增子序列，使得这个递增子序列的最大元素比array[i+1]小，且长度尽量地大。这样将array[i+1]加在该递增子序列后，便可找到以array[i+1]为最大元素的最长递增子序列。

仍然假设在数组的前i个元素中，以array[i]为最大元素的最长递增子序列的长度为LIS[i]。

同时，假设：

长度为1的递增子序列最大元素的最小值为MaxV[1];

长度为2的递增子序列最大元素的最小值为MaxV[2];

……

长度为LIS[i]的递增子序列最大元素的最小值为MaxV[LIS[i]]。

具体算法实现如下：

#include 
  
   
 
#define MAX 100000
#define VMAX 100001
#define MIN (-2147483647 - 1)
 
int BSearch (int MaxV[], int start, int end, int key){
    int mid;
 
    while (start <= end){
        mid = start + ((end - start) >> 1);
        if (MaxV[mid] < key){
            start = mid + 1;
        }
        else if (MaxV[mid] > key){
            end = mid - 1;
        }
        else
            return mid;
    }
    return start;
}
 
int LIS (int data[], int n){
    int MaxV[VMAX];
    MaxV[1] = data[0];
    MaxV[0] = MIN;
    int LIS[MAX];
 
    int nMaxLIS = 1;
    int i, j;
    for (i=0; i
   
     nMaxLIS){ nMaxLIS = LIS[i]; MaxV[LIS[i]] = data[i]; } else if (MaxV[j] < data[i] && data[i] < MaxV[j + 1]){ MaxV[j+1] = data[i]; } } return nMaxLIS; } int main(void){ int data[MAX]; int n; int i; while (scanf (%d, &n) != EOF){ for (i=0; i