大家好，我是苍何。
盼着盼着，又快过年啦，这几天，大厂们的春节假期也陆续出炉，像腾讯、美图、拼多多、和网易就公布了春节放假安排，目前网易的假期最为慷慨，直接就放假 12 天。
具体安排如下:
1、1月26日-1月27日统一扣除2天年假
2、2月5日为公司赠送假期，不占用年假额度
3、福利年假赠送假期无需主动申请，人力统一扣除。
本来想偷偷替网易的家人们乐一会，但仔细一看，虽说放假 12 天，要扣掉 2 天年假（1 月 26 日-1 月 27 日）。
再扣除法定节假日，实际上，网易是多送了 2 天的假期。（1月25日和2月5日）。
你还别看不上这两天，就目前已公布的大厂春节假期来看，已经算是好的了。
相比较之下，腾讯放假时间为1月27日至2月4日，共计9天，就显得普普通通了，除去法定节假日，相当于多给打工人送了一天假期（1 月 27 日）。
再来看看拼夕夕，正常的跟着法定节假日走，一天不多，一天也不少😂
当然还有更自由的假期安排，比如携程，直接就公布了提前返乡政策，不过也只是针对一线客服岗位。
其实每年春节都感觉假期不够用，回个家，没睡几个懒觉，就又要屁颠屁颠跑来上班了，春节作为最重要的节日，我觉得就该多放几天假，享受家人在一起的欢乐时光。
好啦，关于大厂春节放假，你有什么补充的呢？你们公司春节放假几天？欢迎评论区讨论。
...
回归主题。
今天来一道网易开发考过的一道面试算法题，给枯燥的牛马生活加加油😂。
题目描述
平台：LeetCode
题号：300
题目描述：最长递增子序列
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的一个子序列。
示例1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4。
示例2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
2. 解题思路
要解决最长递增子序列的问题，我们可以采用以下两种方法：
动态规划 (DP)
定义
dp[i]表示以第i个元素为结尾的最长递增子序列的长度。初始化：
dp[i] = 1，因为每个元素本身就可以算一个长度为 1 的子序列。状态转移方程：对于每个
j(0 ≤ j < i)，如果nums[j] < nums[i]，那么dp[i] = max(dp[i], dp[j] + 1)。最终结果：
max(dp)即为整个数组的最长递增子序列长度。时间复杂度为 O(n^2)，适合中等规模的输入。
贪心 + 二分查找
如果找到，替换这个位置的值；
如果未找到，说明当前元素比
sub中所有元素都大，直接追加到sub的末尾。
使用一个辅助数组
sub，sub中的元素始终保持递增。遍历
nums数组中的每个元素，使用二分查找找到sub中第一个大于等于当前元素的位置：sub的长度就是最长递增子序列的长度。时间复杂度为 O(n log n)，适合大规模输入。
3. 代码模拟
Java代码：动态规划法 (O(n^2))
public class LongestIncreasingSubsequence {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] dp = new int[n]; // dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度
int maxLength = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1; // 每个元素自身长度为 1
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) { // 当前元素比前面的元素大
dp[i] = Math.max(dp[i], dp[j] + 1); // 更新 dp[i]
}
}
maxLength = Math.max(maxLength, dp[i]); // 更新最长长度
}
return maxLength;
}
}
C++代码：动态规划法 (O(n^2))
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1); // dp[i] 表示以 i 结尾的最长递增子序列长度
int maxLength = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) { // 当前元素比前面的元素大
dp[i] = max(dp[i], dp[j] + 1); // 更新 dp[i]
}
}
maxLength = max(maxLength, dp[i]); // 更新最长长度
}
return maxLength;
}
};
Python代码：动态规划法 (O(n^2))
def length_of_lis(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n # dp[i] 表示以第 i 个元素结尾的最长递增子序列长度
for i in range(n):
for j in range(i):
if nums[j] < nums[i]: # 当前元素比前面的元素大
dp[i] = max(dp[i], dp[j] + 1)
return max(dp) # 返回最长子序列的长度
# 示例
nums = [10,9,2,5,3,7,101,18]
print(length_of_lis(nums)) # 输出: 4
Python代码：贪心 + 二分查找法 (O(n log n))
import bisect
def length_of_lis(nums):
sub = [] # 用于存储递增子序列
for num in nums:
# 二分查找找到第一个 >= num 的位置
pos = bisect.bisect_left(sub, num)
if pos == len(sub):
sub.append(num) # 如果 num 比所有元素都大，追加到末尾
else:
sub[pos] = num # 替换找到的位置
return len(sub) # 最终子序列的长度
# 示例
nums = [10,9,2,5,3,7,101,18]
print(length_of_lis(nums)) # 输出: 4
4. 复杂度分析
动态规划法：
时间复杂度：O(n^2)，其中 n 是数组的长度。
空间复杂度：O(n)，用于存储
dp数组。
贪心 + 二分查找法：
时间复杂度：O(n log n)，其中 n 是数组的长度。二分查找的复杂度为
O(log n)。空间复杂度：O(n)，用于存储递增子序列。
ending
你好呀，我是苍何。是一个每天都在给自家仙人掌讲哲学的执着青年，我活在世上，无非想要明白些道理，遇见些有趣的事。倘能如我所愿，我的一生就算成功。共勉 💪
点击关注下方账号，你将感受到一个朋克的灵魂，且每篇文章都有惊喜。
感谢大家一直以来的阅读、在看和转发，我会把流量主收益都用来发红包，大家可在公众号页面发送相关暗号关键词获取抽奖，每一篇文章会给到一个不同的暗号，对应的抽奖都是独立的，此篇暗号为【春节】，在后台回复【春节】，即可点击进去参与抽奖！抽奖内容、金额、个数等都无变化，在开奖前参与抽奖，操作均有效。
注意，后台（不是评论区，是后台）回复【春节】即可参与抽奖。
后台回复（不是评论区，是后台）即可参与抽奖。
后台回复（不是评论区，是后台）即可参与抽奖。
就像大家之前回复【八股】一样。
