这是一个经典的LIS(即最长上升子序列)问题，请设计一个尽量优的解法求出序列的最长上升子序列的长度。
给定一个序列A及它的长度n(长度小于等于500)，请返回LIS的长度。
测试样例：
[1,4,2,5,3],5
返回：3
class LongestIncreasingSubsequence {
public:
int getLIS(vector<int> A, int n) {
// write code here
vector<int> dp(n, 0);
dp[0] = 1;
int lis = 0;
for(int i=1; i<n; ++i){
int base = 0;
for(int j=i-1; j>=0; --j){
if(A[i] > A[j]){
base = dp[j] > base ? dp[j] : base;
}
}
dp[i] = base + 1;
lis = dp[i] > lis ? dp[i] : lis;
}
return lis;
}
};
