2.16 求數組中最長遞增子序列

題目：

求一個一維數組(N個元素)中最長遞增子序列的長度

DP題

代碼如下：

#include 

using namespace std;

const int MAXN = 100000;
const int INF = 10000000;
int minV[MAXN], lis[MAXN], Array[MAXN];
int n;

//lis[i]表示從第i個元素開始的最長序列的長度
//minV[i]表示所有長度為i的序列中，最大的元素的最小值
//Array這個數組代表的是原始數組

int LIS(int *A, int n) {
	int nMaxLen = 1;     //數組最長遞增子序列的長度
	for(int i = 0; i < n; ++i) lis[i] = 1;      //初始化最長遞增序列的信息   
	minV[0] = -INF;
	minV[1] = A[0];
	for(int i = 1; i < n; ++i) {
		//遍歷歷史最長遞增序列信息
		int j = 0;
		//要提高效率的話，這裡可以改為二分搜索
		for(j = nMaxLen; j >= 0; --j) {
			if(A[i] > minV[j]) {
				lis[i] = j + 1;
				break;
			}
		}
		//如果當前最長序列大於最長遞增序列長度，更新最長信息
		if(lis[i] > nMaxLen) {
			nMaxLen = lis[i];
			minV[nMaxLen] = A[i];
		}else if(A[i] > minV[j] && A[i] < minV[j + 1]) {
			minV[j + 1] = A[i];
		}
	}
	return nMaxLen;
}

int main() {
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> Array[i];
	cout << LIS(Array, n) << endl;
	return 0;
}