来源：编程网事
大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位脉友说华为od开始卡35岁了，估计是身边有因为年龄被od卡的朋友。华为内部员工纷纷来评论区”辟谣“，有一位华为内部员工表示：“辟谣了，不是现在开始卡，而是早就卡了”。也有内部员工表示他们部门负责od招聘的早就说过30的简历就不看了。还有脉友说这肯定是谣言，自己39岁拿到过华为od的offer。
我认为这应该属于公司众多部门里的个例，卡年龄这事估计很多公司干过，候选人供大于求的情况下，筛选简历最粗暴的方式不外乎，学历、年龄甚至是性别。虽然极不负责，但也无可奈何，遇到这种公司或部门不去也罢。
言归正传，今天我们来分享一道华为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中最大的元素就是我们要找的答案。
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());
}
};
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)
特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。
