题目1533：最长上升子序列

本文主要是介绍题目1533：最长上升子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

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

输入：

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

输出：

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

样例输入：

4
4 2 1 3
5
1 1 1 1 1

样例输出：

2
1

本题的主要解题思路请参考：http://blog.csdn.net/dangwenliang/article/details/5728363和http://www.cnblogs.com/liyongmou/archive/2010/07/11/1775341.html。

#include <stdio.h>#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;}elsereturn mid;}return start;
}int LIS (int data[], int n){int MaxV[VMAX];MaxV[1] = data[0];MaxV[0] = MIN;int nMaxLIS = 1;int i, j;for (i=1; i<n; ++i){j = BSearch (MaxV, 0, nMaxLIS, data[i]);if (j > nMaxLIS){nMaxLIS = j;MaxV[j] = data[i];}else if (MaxV[j-1] < data[i] && data[i] < MaxV[j]){MaxV[j] = data[i];}}return nMaxLIS;
}int main(void){int data[MAX];int n;int i;while (scanf ("%d", &n) != EOF){for (i=0; i<n; ++i){scanf ("%d", &data[i]);}printf ("%d\n", LIS (data, n));}return 0;
}

这篇关于题目1533：最长上升子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---