Input
10 9 2 5 3 7 101 18
Output
4 （因?yàn)?,3,7,101是最長的遞增子序列）
解題思路
該問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)鹰服，因此可以使用動態(tài)規(guī)劃求解。
定義如下符號：
-
表示問題序列的總長度昔案。
-
表示下標(biāo)從1到i的一個(gè)序列较雕，特別地随常，
表示下標(biāo)從1開始掩蛤，長度為n的一個(gè)序列，也就是問題的輸入干花。
-
表示
個(gè)元素妄帘。
由于問題的最優(yōu)解必然對應(yīng)某個(gè)子序列，而這個(gè)子序列又必然由某個(gè)結(jié)尾池凄，因此抡驼，由所有
結(jié)尾的最長遞增序列的長度，構(gòu)成了問題的解空間肿仑。因此致盟，再引入符號L，來描述問題的解空間：
-
表示以
顯然勾邦，為該遞增子序列的最大值，
就是問題的最優(yōu)解割择。
求解眷篇，就要得到所有的
。求解
這一問題荔泳，包含了求解從
到
的所有子問題蕉饼，從而滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。
遞歸方程如下：
轉(zhuǎn)換成代碼玛歌，思路就是遍歷所有昧港，選擇滿足
的最大的
，則
支子，如果
比所有
都要小创肥，則
。
完整代碼
Leetcode上面有這個(gè)問題值朋，可以上去檢驗(yàn)一下：
class Solution {
public:
int max(const int &a, const int &b)
{
return a>b?a:b;
}
int lengthOfLIS(vector<int> &nums)
{
int n = nums.size();
int res = 1;
if(nums.size() == 0) return 0;
int *l = new int[n];
l[0] = 1;
for(int i = 1; i < n; i++) //填充L
{
int maxval = 1;
for(int j = 0; j < i; j++) //遍歷所有的A
{
if(nums[i] > nums[j])
{
maxval = max(maxval, l[j]+1);
}
l[i] = maxval;
}
}
for(int i = 0; i < n; i++)
{
if(l[i]>res)
{
res = l[i];
}
}
return res;
}
};
