说实话，作为程序员，我看到这种情况还是挺有感触的。
你说就这学历，为啥要进od呢？这个学历不管是现在还是跳槽，根本不愁找工作。毕竟，“清华姚班”这几个字放在简历上，那都是大厂求之不得的人才呀
说白了，这就是“学历决定命运”。
但这哥们的操作真的有点看不懂呀，你们怎么看？
算法题：非递减子序列
聊一道挺常见的算法题：非递减子序列。
题目大概是这样的：给你一个数组，要求你从中找出一个最长的非递减子序列。你需要返回这个子序列的长度。
首先，我来给大家简单科普一下“非递减子序列”是什么。非递减子序列其实就是一个子序列，满足其中的元素是从左到右按不小于的顺序排列的。换句话说，对于数组 arr = [1, 2, 2, 3, 1]， [1, 2, 2, 3] 就是一个非递减子序列，但 [1, 3, 2] 就不是，因为它违反了顺序。
好了，进入正题。这个问题看起来和最长递增子序列（LIS）很像，但你会发现其实并没有那么复杂。最长递增子序列我们通常用动态规划（DP）来做，非递减子序列其实也是可以用类似的方法来解决。
首先我们定义一个数组 dp，dp[i] 表示以 arr[i] 结尾的最长非递减子序列的长度。起初每个位置的 dp[i] 都是 1，因为每个数字本身至少可以形成一个长度为 1 的非递减子序列。接着，我们就需要遍历数组，对于每个位置 i，检查它之前的所有位置 j（j < i），如果 arr[j] <= arr[i]，那么我们就可以更新 dp[i]，取 dp[i] 和 dp[j] + 1 的较大值，表示将 arr[i] 加到 arr[j] 形成的子序列后面。
看起来是不是很简单？我给大家提供一个 Java 代码示例：
public class LongestNonDecreasingSubsequence {
public static int longestNonDecreasingSubsequence(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int n = arr.length;
int[] dp = new int[n];
// 初始化dp数组，每个位置的初始值为1
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
int maxLength = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] >= arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
public static void main(String[] args) {
int[] arr = {1, 3, 2, 3, 4, 1, 5};
System.out.println("Longest Non-Decreasing Subsequence Length: " + longestNonDecreasingSubsequence(arr));
}
}
在这段代码中，我们使用了动态规划的经典方法，维护了一个 dp 数组，逐步更新每个位置的最大子序列长度。最终，返回 dp 数组中的最大值，即为所求的最长非递减子序列的长度。
你可能会想，诶，这样时间复杂度不就变成了 O(n^2) 吗？对，没错，这是标准的动态规划解法。虽然它的时间复杂度有点高，但是对于大部分题目来说，O(n^2) 也是能接受的。如果数组特别大，性能成了瓶颈，那就可以考虑优化。比如，用二分查找来维护一个数组，以减少时间复杂度，最好的优化方式可以将时间复杂度降低到 O(n log n)。
有个经典的优化思路就是使用一个辅助数组 tail 来模拟最长递增子序列的问题。我们通过二分查找来在 tail 中找到最合适的插入位置，然后更新这个位置的值。这样做的好处是避免了遍历所有的前面元素，大大提升了效率。优化后的代码就像这样：
public class LongestNonDecreasingSubsequenceOptimized {
public static int longestNonDecreasingSubsequence(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int n = arr.length;
int[] tail = new int[n];
int size = 0;
for (int num : arr) {
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tail[mid] <= num) {
left = mid + 1;
} else {
right = mid;
}
}
tail[left] = num;
if (left == size) {
size++;
}
}
return size;
}
public static void main(String[] args) {
int[] arr = {1, 3, 2, 3, 4, 1, 5};
System.out.println("Longest Non-Decreasing Subsequence Length: " + longestNonDecreasingSubsequence(arr));
}
}
这段优化后的代码时间复杂度是 O(n log n)，更加高效了。
其实，每次做这种动态规划的题目，我总是会感叹一句：“写代码真的得细心。”就像我在做这道题时，最开始其实只考虑了 O(n^2) 的暴力解法，结果把自己给绕进去了。直到想到用二分法优化，才恍然大悟，原来能更快。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
