R7-1 最长上升子序列 (15 分)

给定一个序列，求它的一个递增子序列，使它的元素个数尽量多，求该序列的最长上升子序列中元素个数。例如序列1,6,2,5,4,7的最长上升子序列是1,2,5,7或1,2,4,7，则其最长上升子序列中的元素个数为4。

输入格式:

第一行中输入序列的个数（不超过20），第二行中输入每个元素，以空格隔开。

输出格式:

输出该序列中最长上升子序列中的元素个数。

输入样例:

6
1 6 2 5 4 7

输出样例:

4

代码

#include <iostream>
#include <stack>
using namespace std;

int n;
int a[20];
stack<int> st;
int maxlen = 0;

// 深度优先搜索
void dfs(int i)
{
	// 如果按照当前数据线路查到头了,比较当前数据线路的长度与之前所取数据线路,记录最大值
	// 每次搜都是要判断一下这个的
	if (i == n)
	{
		if (st.size() > maxlen)
			maxlen = st.size();
		return;
	}
	// 如果下一个搜索的数组元素大于栈顶  那么把他弄到栈里
	if (st.empty() || a[i] > st.top()) {
		st.push(a[i]);
		// 如果当前元素能行  那么顺着当前元素继续搜索下一条元素
		dfs(i + 1);

		// 上面执行的过程可能很长,能执行到这一步说明  线路已经回退回来了,那么把这个元素弄出去  继续搜索下一个
		st.pop();
	}

	dfs(i + 1);
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	// 从第0层开始搜索
	dfs(0);
	cout << maxlen << endl;

	return 0;
}