好离谱！前米哈游员工自曝，找朋友内推了腾讯的岗位，简历过了，一直没安排面试，突然有一天居然收到短信告知面试失败了

吴师兄学算法 · 公众号 · · 2024-03-16 11:10

正文

大家好，我是吴师兄。

往日里，人们普遍认为，通过熟人内推求职，胜算要比平常途径大得多。确实，这种看法在过去几年里几乎是铁律。但呢，风水轮流转，现在的情况似乎有了些微妙的变化。

这是一位离开了米哈游的朋友分享的，他想跻身腾讯的大家庭。 注意了，他动用的是铁杆朋友的内推资源 ，而不是网络上那些不明来历，或者自称有内推渠道的人。

毕竟，这种通过熟人的内推方式，本质上更为可靠一些。

这位朋友提交了他的简历，然而，日子一天天过去，腾讯那边却杳无音信。

就在他几乎忘记了这件事的时候，一条出人意料的短信悄然而至，告知他面试未通过——这一切发生得太突然，让人措手不及 。

看，即便是在如今这个充满变数的职场里，内推依旧是个不小的加分项，但显然，它已不是唯一的制胜法宝。市场的竞争日趋激烈，无论是内推还是其他途径，都需要我们更加努力，更加全面地展示自己的能力和特点。

这件事给我们的启示是，不论走哪条路，准备工作做得越充分，越能在竞争中脱颖而出，比如准备算法面试，每天刷一两题效果肯定比短时间刷几百题效果更好。

进入今天的算法刷题之旅吧，来做一道 米哈游 相关的面试原题。

题目描述是这样的，给你一个整数数组 nums ，找到其中 最长严格递增子序列的长度 。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

这个问题要求找到给定数组 nums 中最长的递增子序列的长度。这里的 "递增" 是指每个后续元素都严格大于前面的元素。关键在于，递增子序列不必是连续的。思路如下：

遍历 nums 数组，对于每个 i （从 1 开始遍历到 nums.length - 1 ），再遍历 i 之前的所有元素 j （从 0 开始遍历到 i-1 ）。
对于每个 j ，如果 nums[i] 大于 nums[j] ，则 nums[i] 可以接在 nums[j] 形成的递增子序列之后。这时，我们比较 dp[i] 和 dp[j] + 1 ，取较大值更新 dp[i] 。这里 dp[j] + 1 表示以 nums[j] 结尾的递增子序列加上 nums[i] 形成的新序列长度。
这个过程会确保每一步都计算出以当前 nums[i] 结尾的最长递增子序列的长度，并存储在 dp[i] 中。

在遍历过程中，通过一个额外的变量 maxLength 记录遍历到目前为止所找到的最长递增子序列的长度。每当 dp[i] 的值被更新时，比较并可能更新 maxLength 。

这种方法的时间复杂度是 O(n^2)，其中 n 是数组 nums 的长度。

这是因为需要双层循环来构建 dp 数组。

虽然这不是解决这个问题最高效的方法（还有 O(n log n) 的解法），但它直观且易于理解，特别适合初学者学习动态规划的思想 。