最长上升子序列（LIS)

最长上升子序列（LIS)问题：给定一个数组，问其最长的单调上身子序列有多长。
这里的单调上升是非严格的，[1,2,2,3]也算单调上升
样例：[1，5，2，3，8，6，7，4]的LIS是[1，2，3，6，7]，长度为5。
如何设计状态？如何设计转移？

这种在序列上求某个东西，我们一般把它叫做序列dp或者线性dp

f(k)表示【以ak结尾的上身子序列，最长的长度】
那么，如何设计转移？

[1，5，2，3，8，6，7，4]
f[7]:
从f[1]过来：1，7
从f[2]过来：1，5，7
从f[3]过来：1，2，7
从f[4]过来：1，2，3，7
不能从f[5]过来，因为f[5]表示的是以a[5]=8结尾的lis长度，7不能拼在8后面
从f[6]过来：1，2，3，6，7

因此我们可以总结出状态转移方程
f(k)=max(f(i)+1),i

 1 #include
 2 using namespace std;
 3 const int N=1010;
 4 int a[N],dp[N];
 5 int main()
 6 {
 7     int n;
 8     cin>>n;
 9     for(int i=1;i<=n;i++)
10     {
11         cin>>a[i];
12     }
13     for(int i=1;i<=n;i++)
14     {
15         dp[i]=1;
16         for(int j=1;j)
17         {
18             if(a[j]<=a[i])
19                 dp[i]=max(dp[i],dp[j]+1);
20         }
21     }
22     int ans=0;
23     for(int i=1;i<=n;i++)
24     {
25         ans=max(ans,dp[i]);
26     }
27     cout<endl;
28     return 0;
29 }