這是一個(gè)經(jīng)典的LIS(即最長(zhǎng)上升子序列)問(wèn)題,請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡量?jī)?yōu)的解法求出序列的最長(zhǎng)上升子序列的長(zhǎng)度搔体。
給定一個(gè)序列A及它的長(zhǎng)度n(長(zhǎng)度小于等于500)恨樟,請(qǐng)返回LIS的長(zhǎng)度。
測(cè)試樣例:
[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;
}
};