大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位脉友说华为od开始卡35岁了，估计是身边有因为年龄被od卡的朋友。华为内部员工纷纷来评论区”辟谣“，有一位华为内部员工表示：“辟谣了，不是现在开始卡，而是早就卡了”。也有内部员工表示他们部门负责od招聘的早就说过30的简历就不看了。还有脉友说这肯定是谣言，自己39岁拿到过华为od的offer。
我认为这应该属于公司众多部门里的个例，卡年龄这事估计很多公司干过，候选人供大于求的情况下，筛选简历最粗暴的方式不外乎，学历、年龄甚至是性别。虽然极不负责，但也无可奈何，遇到这种公司或部门不去也罢。
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道华为od的面试原题「最长递增子序列」。
题目描述
给你一个整数数组nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
举个例子：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是[2,3,7,101]，因此长度为 4。
思路解析
下图给出了nums = [1, 4, 3]枚举最长递增子序列的过程，每个节点都是nums的一个子序列。
从上图可以看出题目其实就是要求从根节点到合法节点的最长路径，其中合法节点中的数组是递增序列，绿色节点表示合法节点。
下面介绍一下动态规划的解法。
动态规划的核心步骤是推导状态转移公式和边界条件处理。
首先定义dp[i]表示以nums第i个元素结尾的最长递增子序列的长度。
以nums = [1, 4, 3]这个例子我们来看下寻找最长递增子序列的过程。
以 第0个元素1结尾的子序列为[1]，其中递增子序列为[1]，所以dp[0] = 1。以 第1个元素4结尾的子序列为[1, 4]、[4]，其中递增子序列为[1, 4]、[4]，所以dp[1] = 2。以 第2个元素3结尾的子序列为[1, 3]、[1, 4, 3]、[4, 3]、[3]，其中递增子序列为[1, 3]、[3]，所以dp[2] = 2。
从上面可以看出我们在求dp[i]时，nums[i]需要和nums[0] ~ nums[i-1]进行比较，如果满足nums[i] > nums[k]，那么dp[i] = max(dp[i], dp[k] + 1)，其中0 <= k < i。
对于 dp[0]，很显然dp[0] = 1。对于 dp[1]，存在nums[1] > nums[0]，所以dp[1] = max(dp[1], dp[0] + 1) = 2。对于 dp[2]，存在nums[2] > nums[0]，所以dp[2] = max(dp[2], dp[0] + 1) = 2。
扩展到一般情况可以得到状态转移公式：
dp[n] = max{dp[0] + 1, ...,dp[i] + 1，dp[n]}
其中0 <= i < n，且nums[n] > nums[i]。
接下来看下边界条件，nums的每个元素都各自为一个长度为1的子序列，故可以初始定义dp[i] = 1。
最终dp中最大的元素就是我们要找的答案。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
int lengthOfLIS(vector<int> & nums) {
int nums_len = nums.size();
//边界条件初始化
vector<int> dp(nums_len, 1);
for (int i = 0; i < nums_len; ++i) {
for (int j = 0; j < i; ++j) {
//状态转移公式
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};
python代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
nums_len = len(nums)
# 边界条件初始化
dp = [1] * nums_len
for i in range(nums_len):
for j in range(i):
# 状态转移公式
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
复杂度分析
时间复杂度: O(n2)，其中n为nums的长度。
空间复杂度： O(n)， 其中n为nums的长度。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
