例题：LeetCode 第 300 题：Longest Increasing Subsequence
传送门：英文网址：300. Longest Increasing Subsequence ，中文网址：300. 最长上升子序列 。
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明:
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
分析：首先仔细审题，明确题目中的条件。
1、子序列：不要求连续子序列，只要保证元素前后顺序一致即可；
2、上升：这里的“上升”是“严格上升”，类似于 [2, 3, 3, 6, 7] 这样的子序列是不符合要求的；
一个序列可能有多个最长上升子序列，题目中只要我们求这个最长的长度。如果使用回溯搜索，选择所有的子序列进行判断，时间复杂度为 。
思路1：动态规划。这个问题具有“最优子结构”。
定义状态：LIS(i) 表示以第 i 个数字为结尾的最长上升子序列的长度。即在 [0, ..., i] 的范围内，选择以数字 nums[i] 结尾可以获得的最长上升子序列的长度。关键字是：以第 i 个数字为结尾，即我们要求 nums[i] 必须被选取。反正一个子序列一定要以一个数字结尾，那我就将状态这么定义，这一点是重要且常见的。
状态转移方程：遍历到索引是 i 的数的时候，我们应该把索引是 [0, ... ,i - 1] 的 LIS 都看一遍，如果当前的数 nums[i] 大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的 LIS 。把前面的 i 个数都看了， LIS[i] 就是它们的最大值加 。即比当前数要小的那些里头，找最大的，然后加
。
状态转移方程即：LIS(i) = max( 1 + LIS(j) if j < i and nums[i] > nums[j])
最后不要忘了，应该扫描一遍这个 LIS[i] 数组，其中最大的就是我们所求的。
我们以下面的数组为例进行说明：
例如：[10，9，2，5，3，7，101，18]。
填表：
| 原始数组 | 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 |
最关键的就是填这张表，其实并不难。最后，我们把整个数组扫描一遍，就找到了最大值。
又例如：[10，15，20，11，9，101]。
| 原始数组 | 10 | 15 | 20 | 11 | 9 | 101 |
|---|---|---|---|---|---|---|
| LIS 刚开始的值 | 1 | 1 | 1 | 1 | 1 | 1 |
| LIS 最后的值 | 1 | 2 | 3 | 2 | 1 | 4 |
Python 代码：关键：找它前面比他小的那些数中最大的
class Solution:
# 动态规划的思路：将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度
# 那么题目要求的，就是这个 dp 数组中的最大者
# 以数组 [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 问题的 解法请看 这里。如果用二分法解决，其中含有贪心思想（因为在一个更小的数后面，才有可能接更大的数。规律：如果比最后一个大，直接接在后面，否则就要执行一次更新操作：找到第 1 个比它大的数，更新它）
例如：1 2 3 4 5 7（更新成 6） 7 7 7 7 7 8 9 来了一个 6。
记忆化递归的解法。有 复杂度的解法。
思路：自己写一个辅助数组，用二分查找完成数组的覆盖或者插入，遍历完整个输入数组，辅助数组的长度就是所求。其实这道题的一个子过程就是 LeetCode 第 35 题：搜索插入位置。这个思路用到的策略是贪心算法，技巧和二分查找。
关键在于找大于等于“当前遍历的那个数”的第 1 个索引，将它替换成“当前遍历的那个数”，这样使得这个数变小，后面才有可能接一个更大的数。
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 个数
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)
说明：这道题还可以用动态规划来完成。
练习：LeetCode 第 376 题：摆动序列
传送门：376. 摆动序列。
一个序列，它的相邻数字的大小关系是升序降序轮流交替的（最初可以是升序，也可以是降序），就称为wiggle sequence。比如[1, 7, 4, 9, 2, 5] 就是一个wiggle sequence。但是[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 就不是。给出一个数组，求出他的最长 wiggle sequence 子序列。
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如，
[1,7,4,9,2,5]是一个摆动序列，因为差值(6,-3,5,-7,3)是正负交替出现的。相反,[1,4,7,2,5]和[1,7,4,5,5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 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) 时间复杂度完成此题?
思路1：状态机。贪心算法，每一次都让非严格上升或者非严格下降的长度最长，这样后面遇到一个下降的元素才会使得摇摆的序列变得更长。
注意：初始状态不能单独拿出来判断，因为有这种特例：[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 表示初始状态，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：动态规划。抓住一点：增加之后，再增加，最长摇摆子序列的长度不变，只有减少了最长摇摆子序列的长度才会加 1。
up[i]：到第 i 个元素为止最后状态是“上升”的最长“摆动”序列长度；
down[i]：到第 i 个元素为止最后状态是“下降”的最长“摆动”序列长度；
遍历数组，从第 2 个元素开始（即索引为 1 开始）比较它与前一个元素的值。
如果 nums[i - 1] < nums[i]，表明第 i - 1 到第 i 个元素是上升的，因此 up[i] 只需在down[i-1] 的基础上加 即可，而
down[i] 保持不变，即 down[i] = down[i - 1]。
总结一下：
如果它大于前一个元素，就根据 down 数组的最后一个值更新 up 数组的值；
如果它小于前一个元素，就根据 up 数组的最后一个值更新 down 数组的值；
如果它等于前一个元素，两个数组的值都不更新。
Python 代码：
class Solution:
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size == 0:
return 0
# 从第 2 个元素开始，当前元素比上一个元素大的时候，能够构成的最长摇摆子序列的长度，否则，该值与之前的值相等
up = [0 for _ in range(size)]
# 从第 2 个元素开始，当前元素比上一个元素小的时候，能够构成的最长摇摆子序列的长度，否则，该值与之前的值相等
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]:
# 上升：表示当前这个元素可以接在 down 所表示的最长摇摆子序列的最后一个，构成一个更长的子序列
# 此时更新 up 的值，它根据 down 的最后一个 + 1
# 理解这一步很关键，这一步理解清楚了，其它两个分支就自然清楚了
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])
因为状态只与前一个值有关，于是有下面更节约空间复杂度的写法。
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)
（本节完）
