最长单调自增子序列：给定一个长度为n的数组，找出一个最长的单调自增子序列，输出最长单调自增子序列的长度（不一定连续，但是顺序不能乱）。

题目描述：

给定一个长度为n的数组，找出一个最长的单调自增子序列，输出最长单调自增子序列的长度（不一定连续，但是顺序不能乱）。

解题思路：

动态规划

定义状态：dp[i]表示以第i个元素结尾的最长单调自增子序列的长度。

状态转移方程：dp[i] = max(dp[j])+1，其中j<i且a[j]<a[i]。

最终答案：max(dp[i])，其中≤i<n。

时间复杂度：O(n^2)

代码实现：

int LIS(int a[], int n)
{
int dp[n];
int ans = 1;
for(int i=; i<n; i++)
{
dp[i] = 1;
for(int j=; j<i; j++)
{
if(a[j]<a[i])
{
dp[i] = max(dp[i], dp[j]+1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}