最长上升子序列(LIS)
前情提要
子串：连续的
子序列：非连续，但相对序的
抛出示例
1 5 2 3 9 5 2 4 等8个数a[8]
前1个数构成的LIS: 最长是1。 子序列为：1
前2个数构成的LIS: 最长是2。 子序列为：1 5
前3个数构成的LIS: 最长是2。 子序列为：1 5或1 2（但我们只考虑1 2）
前4个数构成的LIS: 最长是3。 子序列为：1 2 3
前5个数构成的LIS: 最长是4。 子序列为：1 2 3 9
前6个数构成的LIS: 最长是4。 子序列为：1 2 3 5
前7个数构成的LIS: 最长是2。 子序列为：1 2（此处的2是第七个位置的2）
前8个数构成的LIS: 最长是4。 子序列为：1 2 3 4
答案是8个数中最长的即4
我们发现8次计算中子序列最后一位数字是当前的数字a[i]，因为我们只考虑这个位置之前的，且比这个位置小的数
用dp[i] 表示前i个数字，以a[i]结尾的最长上升子序列
转移方程 dp[i]=max(dp[i],dp[j]+1) 其中(1<=j<i且a[j]<a[i])
初始化 dp[i]表示前i个，但是如果前面没有比a[i]，小的，那么dp[i]=1,子序列：a[i]。即dp[i]的初始值为1
答案就是dp[i]中最大的一个数
解决算法O(n2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5555;//一般只能几千数量级
ll a[N];
ll dp[N];
//dp[i]，表示前i个数字，
//以a[i]结尾的最长上升子序列长度
void solve()
{
ll n,ans=0;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
dp[i]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[j]<a[i])
{
dp[i]=max(dp[i],dp[j]+1);
}
}
ans=max(ans,dp[i]);
}
cout<<ans;
}
int main()
{
solve();
}