例題：LeetCode 第 300 題：Longest Increasing Subsequence
傳送門：英文網(wǎng)址：300. Longest Increasing Subsequence ，中文網(wǎng)址：300. 最長上升子序列 矾芙。
給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度斗锭。
示例:
輸入: [10,9,2,5,3,7,101,18] 輸出: 4 解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。說明:
- 可能會有多種最長上升子序列的組合金赦，你只需要輸出對應(yīng)的長度即可兔朦。
- 你算法的時間復(fù)雜度應(yīng)該為 O(n2) 。
進階: 你能將算法的時間復(fù)雜度降低到 O(n log n) 嗎?
分析：首先仔細(xì)審題恨诱，明確題目中的條件兢仰。
1忆矛、子序列：不要求連續(xù)子序列绞铃，只要保證元素前后順序一致即可；
2、上升：這里的“上升”是“嚴(yán)格上升”奴璃，類似于 [2, 3, 3, 6, 7] 這樣的子序列是不符合要求的跟磨；
一個序列可能有多個最長上升子序列叹话，題目中只要我們求這個最長的長度热凹。如果使用回溯搜索碟渺，選擇所有的子序列進行判斷蔬捷，時間復(fù)雜度為 。
思路1：動態(tài)規(guī)劃旅择。這個問題具有“最優(yōu)子結(jié)構(gòu)”畜眨。
定義狀態(tài)：LIS(i) 表示以第 i 個數(shù)字為結(jié)尾的最長上升子序列的長度。即在 [0, ..., i] 的范圍內(nèi)载庭，選擇以數(shù)字 nums[i] 結(jié)尾可以獲得的最長上升子序列的長度。關(guān)鍵字是：以第 i 個數(shù)字為結(jié)尾优质，即我們要求 nums[i] 必須被選取。反正一個子序列一定要以一個數(shù)字結(jié)尾票灰，那我就將狀態(tài)這么定義，這一點是重要且常見的。
狀態(tài)轉(zhuǎn)移方程：遍歷到索引是 i 的數(shù)的時候句旱，我們應(yīng)該把索引是 [0, ... ,i - 1] 的 LIS 都看一遍稚配，如果當(dāng)前的數(shù) nums[i] 大于之前的某個數(shù)，那么 nums[i] 就可以接在這個數(shù)后面形成一個更長的 LIS 崖技。把前面的 i 個數(shù)都看了翼闽， LIS[i] 就是它們的最大值加 古徒。即比當(dāng)前數(shù)要小的那些里頭拓提，找最大的，然后加
隧膘。
狀態(tài)轉(zhuǎn)移方程即：LIS(i) = max( 1 + LIS(j) if j < i and nums[i] > nums[j])
最后不要忘了代态，應(yīng)該掃描一遍這個 LIS[i] 數(shù)組，其中最大的就是我們所求的疹吃。
我們以下面的數(shù)組為例進行說明：
例如：[10蹦疑，9，2萨驶，5歉摧，3，7，101叁温，18]再悼。
填表：
| 原始數(shù)組 | 10 | 9 | 2 | 5 | 3 | 7 | 101 | 18 |
|---|---|---|---|---|---|---|---|---|
| LIS 剛開始的值 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| LIS 最后的值 | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 4 |
最關(guān)鍵的就是填這張表，其實并不難膝但。最后冲九，我們把整個數(shù)組掃描一遍，就找到了最大值跟束。
又例如：[10莺奸，15，20冀宴，11灭贷，9，101]花鹅。
| 原始數(shù)組 | 10 | 15 | 20 | 11 | 9 | 101 |
|---|---|---|---|---|---|---|
| LIS 剛開始的值 | 1 | 1 | 1 | 1 | 1 | 1 |
| LIS 最后的值 | 1 | 2 | 3 | 2 | 1 | 4 |
Python 代碼：關(guān)鍵：找它前面比他小的那些數(shù)中最大的
class Solution:
# 動態(tài)規(guī)劃的思路：將 dp 數(shù)組定義為：以 nums[i] 結(jié)尾的最長上升子序列的長度
# 那么題目要求的氧腰，就是這個 dp 數(shù)組中的最大者
# 以數(shù)組 [10, 9, 2, 5, 3, 7, 101, 18] 為例：
# dp 的值： 1 1 1 2 2 3 4 4
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size <= 1:
return size
dp = [1] * size
for i in range(1, size):
for j in range(i):
if nums[i] > nums[j]:
# + 1 的位置不要加錯了
dp[i] = max(dp[i], dp[j] + 1)
# 最后要全部走一遍，看最大值
return max(dp)
Java 代碼：
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if (len < 2) {
return len;
}
int[] dp = new int[len];
// 自己一定是一個子序列
Arrays.fill(dp, 1);
for (int i = 1; i < len; i++) {
// 看以前的刨肃，比它小的古拴，說明可以接在后面形成一個更長的子序列
// int curMax = Integer.MIN_VALUE; 不能這樣寫，萬一前面沒有比自己小的真友，
// 這個值就得不到更新
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
}
int res = dp[0];
for (int i = 0; i < len; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
}
LIS 問題的 解法請看 這里黄痪。如果用二分法解決，其中含有貪心思想（因為在一個更小的數(shù)后面盔然，才有可能接更大的數(shù)桅打。規(guī)律：如果比最后一個大，直接接在后面愈案，否則就要執(zhí)行一次更新操作：找到第 1 個比它大的數(shù)挺尾，更新它）
例如：1 2 3 4 5 7（更新成 6） 7 7 7 7 7 8 9 來了一個 6。
記憶化遞歸的解法站绪。有 復(fù)雜度的解法遭铺。
思路：自己寫一個輔助數(shù)組，用二分查找完成數(shù)組的覆蓋或者插入恢准，遍歷完整個輸入數(shù)組魂挂，輔助數(shù)組的長度就是所求。其實這道題的一個子過程就是 LeetCode 第 35 題：搜索插入位置馁筐。這個思路用到的策略是貪心算法涂召，技巧和二分查找。
關(guān)鍵在于找大于等于“當(dāng)前遍歷的那個數(shù)”的第 1 個索引敏沉，將它替換成“當(dāng)前遍歷的那個數(shù)”果正，這樣使得這個數(shù)變小炎码，后面才有可能接一個更大的數(shù)。
Python 代碼：
class Solution:
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size < 2:
return size
# 最長上升子序列
lis = []
for num in nums:
# 找到大于等于 target 的第 1 個數(shù)
l = 0
r = len(lis)
while l < r:
mid = l + (r - l) // 2
if lis[mid] >= num:
r = mid
else:
l = mid + 1
if l == len(lis):
lis.append(num)
else:
lis[l] = num
return len(lis)
if __name__ == '__main__':
nums = [10, 9, 2, 5, 3, 7, 101, 18]
solution = Solution()
result = solution.lengthOfLIS(nums)
print(result)
說明：這道題還可以用動態(tài)規(guī)劃來完成舱卡。
練習(xí)：LeetCode 第 376 題：擺動序列
傳送門：376. 擺動序列辅肾。
一個序列队萤，它的相鄰數(shù)字的大小關(guān)系是升序降序輪流交替的（最初可以是升序轮锥，也可以是降序），就稱為wiggle sequence要尔。比如[1, 7, 4, 9, 2, 5] 就是一個wiggle sequence舍杜。但是[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 就不是。給出一個數(shù)組赵辕，求出他的最長 wiggle sequence 子序列既绩。
如果連續(xù)數(shù)字之間的差嚴(yán)格地在正數(shù)和負(fù)數(shù)之間交替，則數(shù)字序列稱為擺動序列还惠。第一個差（如果存在的話）可能是正數(shù)或負(fù)數(shù)饲握。少于兩個元素的序列也是擺動序列。
例如蚕键，
[1,7,4,9,2,5]是一個擺動序列救欧，因為差值(6,-3,5,-7,3)是正負(fù)交替出現(xiàn)的。相反,[1,4,7,2,5]和[1,7,4,5,5]不是擺動序列锣光，第一個序列是因為它的前兩個差值都是正數(shù)笆怠，第二個序列是因為它的最后一個差值為零。給定一個整數(shù)序列誊爹，返回作為擺動序列的最長子序列的長度蹬刷。 通過從原始序列中刪除一些（也可以不刪除）元素來獲得子序列，剩下的元素保持其原始順序频丘。
示例 1:
輸入: [1,7,4,9,2,5] 輸出: 6 解釋: 整個序列均為擺動序列办成。示例 2:
輸入: [1,17,5,10,13,15,10,5,16,8] 輸出: 7 解釋: 這個序列包含幾個長度為 7 擺動序列，其中一個可為[1,17,10,13,10,16,8]搂漠。示例 3:
輸入: [1,2,3,4,5,6,7,8,9] 輸出: 2進階:
你能否用 O(n) 時間復(fù)雜度完成此題?
思路1：狀態(tài)機迂卢。貪心算法，每一次都讓非嚴(yán)格上升或者非嚴(yán)格下降的長度最長状答，這樣后面遇到一個下降的元素才會使得搖擺的序列變得更長冷守。
注意：初始狀態(tài)不能單獨拿出來判斷，因為有這種特例：[1,1,1,1,17,5,10,13,15,10,5,16,8]惊科。
Python 代碼：
class Solution:
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size < 2:
return size
# [1,17,5,10,13,15,10,5,16,8]
# 0 表示初始狀態(tài)拍摇，1 表示上升，2 表示下降
res = 1
state = 0
for i in range(1, size):
if state == 0:
if nums[i - 1] > nums[i]:
res += 1
state = 2
continue
if nums[i - 1] < nums[i]:
state = 1
res += 1
continue
if state == 1 and nums[i - 1] > nums[i]:
res += 1
state = 2
continue
if state == 2 and nums[i - 1] < nums[i]:
res += 1
state = 1
return res
if __name__ == '__main__':
solution = Solution()
nums = [1, 1, 7, 4, 9, 2, 5]
result = solution.wiggleMaxLength(nums)
print(result)
思路2：動態(tài)規(guī)劃馆截。抓住一點：增加之后充活，再增加蜂莉，最長搖擺子序列的長度不變，只有減少了最長搖擺子序列的長度才會加 1混卵。
up[i]：到第 i 個元素為止最后狀態(tài)是“上升”的最長“擺動”序列長度映穗；
down[i]：到第 i 個元素為止最后狀態(tài)是“下降”的最長“擺動”序列長度；
遍歷數(shù)組幕随，從第 2 個元素開始（即索引為 1 開始）比較它與前一個元素的值蚁滋。
如果 nums[i - 1] < nums[i]，表明第 i - 1 到第 i 個元素是上升的赘淮，因此 up[i] 只需在down[i-1] 的基礎(chǔ)上加 即可辕录，而
down[i] 保持不變，即 down[i] = down[i - 1]梢卸。
總結(jié)一下：
如果它大于前一個元素走诞，就根據(jù) down 數(shù)組的最后一個值更新 up 數(shù)組的值；
如果它小于前一個元素蛤高，就根據(jù) up 數(shù)組的最后一個值更新 down 數(shù)組的值蚣旱；
如果它等于前一個元素，兩個數(shù)組的值都不更新戴陡。
Python 代碼：
class Solution:
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size == 0:
return 0
# 從第 2 個元素開始塞绿，當(dāng)前元素比上一個元素大的時候，能夠構(gòu)成的最長搖擺子序列的長度猜欺，否則位隶，該值與之前的值相等
up = [0 for _ in range(size)]
# 從第 2 個元素開始，當(dāng)前元素比上一個元素小的時候开皿，能夠構(gòu)成的最長搖擺子序列的長度涧黄，否則，該值與之前的值相等
down = [0 for _ in range(size)]
up[0] = 1
down[0] = 1
for i in range(1, size):
if nums[i - 1] < nums[i]:
# 下降
up[i] = up[i - 1]
down[i] = up[i - 1] + 1
elif nums[i - 1] > nums[i]:
# 上升：表示當(dāng)前這個元素可以接在 down 所表示的最長搖擺子序列的最后一個赋荆，構(gòu)成一個更長的子序列
# 此時更新 up 的值笋妥，它根據(jù) down 的最后一個 + 1
# 理解這一步很關(guān)鍵，這一步理解清楚了窄潭，其它兩個分支就自然清楚了
up[i] = down[i - 1] + 1
down[i] = down[i - 1]
else:
up[i] = up[i - 1]
down[i] = down[i - 1]
return max(up[-1], down[-1])
因為狀態(tài)只與前一個值有關(guān)春宣，于是有下面更節(jié)約空間復(fù)雜度的寫法。
Python 代碼：
class Solution:
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size == 0:
return 0
up = 1
down = 1
for i in range(1, size):
if nums[i - 1] < nums[i]:
down = up + 1
elif nums[i - 1] > nums[i]:
up = down + 1
return max(up, down)
（本節(jié)完）
