最长递增子序列（LIS）

问题

---

给定一个序列a，找到一个最长的子序列，使得子序列中的元素严格单调递增（后一个元素大于等于前一个元素）。

样例

---

输入：
10, 22, 9, 33, 21, 50, 41, 60, 80
输出：
6 (10, 22, 33, 41(50), 60 , 80)

解法

---

设dp[i]为以第i个元素为结尾的的最长递增子序列的长度。
对于每一个i，遍历j ∈ [0, i - 1]，如果a[i] > a[j]，说明a[i]可以接到以a[j]为结尾的序列的后面，并检查是否该新序列是否最长，则有：$dp[i]=\max (dp[i],dp[j]+1)$
初始状态：每个元素本身就是长度为1的子序列，整个dp数组初始化为1。

模版

---

int n, N;
int a[N], dp[N];
 
int LIS()
{
	int res = 1;
	for(int i = 1; i <= n; i++)
		dp[i] = 1;
	
	for(int i = 2; i <= n; i++)
		for(int j = 1; j < i; i++)
			if(a[i] > a[j])
				dp[i] = std::max(dp[i], dp[j] + 1);
	
	for(int i = 1; i <= n; i++)
		res = std::max(res, dp[i]);
		
	return res;
}