凌晨两点还在改bug，已婚同事突然发消息:“老公送宵夜来了，分你一半不？破防了

刚看到个贴子，说程序员凌晨两点还在改bug，已婚同事发来消息：“老公送宵夜来了，分你一半不？”那一瞬间他破防了。 

网友有的酸、有的羡慕，但从程序员角度看，这不仅是情绪触动，也是提醒——别让工作吞掉了生活。 长期熬夜加班，CPU再高频也会过热，更何况是人。技术债可以重构，身体和关系的债可没那么容易还。

羡慕归羡慕，但更要想办法给自己留点“宵夜时刻”，哪怕是自己买杯奶茶，也算是对自己加个生活的断点调试。 总的来说，写代码是谋生，过日子才是本质，别让生活的主线程被bug线程死锁了。【备注:文末可领最新资料】

算法题：最长递增子序列

前两天在公司茶水间聊天，隔壁组的小王突然冒出来一句：“哥，我面试被问了个最长递增子序列，我脑袋一热就说成排序了，结果凉了。” 我当时差点笑喷咖啡，心里想这玩意确实名字听着高大上，其实拆开来看就是一句话：在一个数组里找一条越来越大的数列，长度要最长。

比如 [10, 9, 2, 5, 3, 7, 101, 18]，你能找到的最长递增子序列是 [2, 3, 7, 101]，长度是 4。注意哦，这里不是连续子数组，中间可以跳着选，只要顺序不乱。

最笨但好理解的方法

说人话就是，咱们先不管性能，暴力试一遍。 用递归或者回溯，每个数字都有两种选择：要它或者不要它。要是你一股脑儿试下来，时间复杂度直接 O(2^n)，小数据还能跑，大了直接卡死。

不过面试一般不会让你真写暴力，他们想看的是你能不能想到 动态规划（DP）。

动态规划版：一步步累起来

思路其实很朴素：

• 我用一个 dp[i] 表示以第 i 个元素结尾的最长递增子序列长度
• 那么我就得看看 i 前面的每个 j，如果 nums[j] < nums[i]，说明我可以接到 j 后面，那 dp[i] = max(dp[i], dp[j] + 1)
• 最后取 dp 数组里的最大值，就是答案

代码长这样：

publicintlengthOfLIS(int[] nums){
if (nums == null || nums.length == 0) return0;
int n = nums.length;
int[] dp = newint[n];
int maxLen = 1;
for (int i = 0; i < n; i++) {
        dp[i] = 1; // 每个数至少能单独成一个序列
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
return maxLen;
}

这个方法的时间复杂度是 O(n²)，一般数组长度几千以内都能稳跑。面试里写这个就算合格。

进阶版：O(n log n) 的二分插牌法

有些大厂面试官会追问：“能优化吗？” 其实可以的，我们用一个数组 tails，它的第 k 个元素代表长度为 k+1 的递增子序列的末尾最小值。

怎么操作呢？

• 遍历 nums，对每个数用二分法找它该插到 tails 的哪个位置
• 如果它比 tails 最后一个还大，就直接加到尾巴上
• 如果它能替换掉中间某个位置的数，就替换掉，这样后面更容易拼长的序列

代码像这样：

publicintlengthOfLIS(int[] nums){
int[] tails = newint[nums.length];
int size = 0;
for (int num : nums) {
int left = 0, right = size;
while (left < right) {
int mid = (left + right) / 2;
if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        tails[left] = num;
if (left == size) size++;
    }
return size;
}

这个方法时间复杂度 O(n log n)，数据大了优势就出来了。

说点实际的

讲真，最长递增子序列这个题，生活里直接遇到的概率不大，但它的思想很常用：

• 做版本升级路径规划
• 排序问题中的耐心排序（Patience Sorting）
• 股票买卖的多段利润问题（稍加改造）

我一般建议面试的时候，先说自己会 O(n²) 的 DP，再补一句“其实还能用二分法做到 O(n log n)”，这样既不显得卖弄，又能加分。