Dynamic Programming(DP)之LIS(Longest Increasing Subsequence)/最长上升子序列

问题描述：给定一个长度为K的数列A，求数值单调递增的子序列的长度最长是多少。A的任意子序列B可表示为B＝{Ak1，Ak2，...}，其中k1<k2<...。

状态表示：b[i]表示以A[i]为结尾的“最长上升子序列”的长度

阶段划分：子序列的结尾位置(数列A中的位置，从前到后)

转移方程：b[i]＝max{b[j]+1}(0≤j<i,A[j]<A[i])

边界：b[0]＝0

目标：max{b[i]}1≤i≤N

代码实现：

#include<bits/stdc++.h>
using namespace std;
int k;
int a[11011];
int b[11011];
int ans;
int main(){
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>a[i];
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<i;j++){
			if(a[i]>a[j]){
				b[i]=max(b[i],b[j]);
			}
		}
		b[i]++;
		ans=max(ans,b[i]);
	}
	cout<<ans<<endl;
	return 0;
}