12_6最长上升子序列LIS

这是一个经典的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;
    }
};