最长递增子序列

题目要求

给定一个整数数组 nums，任务是找出这个数组中最长的严格递增子序列的长度。所谓的子序列是指可以通过删除原数组中的某些元素（也可以一个都不删），得到的一个新序列。在这个新序列中，元素的相对顺序保持不变。严格递增意味着子序列中的每个后续元素都比前一个元素大。

解题思路

解决这个问题的一个经典方法是使用动态规划。动态规划的基本思想是将问题分解成一系列相关的子问题，然后从最简单的子问题开始解决，逐步得到原问题的解。

初始化状态数组： 创建一个长度与原数组 nums 相同的数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始时，每个元素的最长递增子序列至少包含它自己，所以将 dp 数组的所有元素初始化为 1。
构建状态转移方程： 遍历数组 nums，对于每个元素 nums[i]，再遍历其之前的所有元素 nums[j]（其中 j < i），如果 nums[j] < nums[i]，说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列之后形成一个新的递增子序列。此时，我们应该更新 dp[i]，使其成为所有可能的递增子序列长度中的最大值，即 dp[i] = max(dp[i], dp[j] + 1)。
遍历状态数组： 在填充完整个 dp 数组后，最长递增子序列的长度即为 dp 数组中的最大值。
优化： 如果需要进一步优化时间复杂度，可以使用二分查找的方法来优化内层循环。具体来说，可以维护一个数组 tails，其中 tails[k] 存储长度为 k+1 的所有递增子序列的最小末尾元素。通过二分查找在 tails 中找到 nums[i] 应该插入的位置，可以在 O(log n) 的时间复杂度内完成更新，从而将总体时间复杂度降低到 O(n log n)。

通过上述步骤，我们可以得到数组 nums 中最长严格递增子序列的长度。

Golang 版本

package main

import "fmt"

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    dp := make([]int, len(nums))
    maxLen := 1

    for i := range dp {
        dp[i] = 1
    }

    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        maxLen = max(maxLen, dp[i])
    }

    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
    fmt.Println("Length of LIS is:", lengthOfLIS(nums))
}

这段代码实现了动态规划的方法来解决最长递增子序列的问题。它首先检查输入数组是否为空，然后初始化一个与输入数组相同长度的 dp 数组，用于存储到当前位置为止的最长递增子序列的长度。接着，它通过两层循环来填充 dp 数组，并在过程中记录下最长递增子序列的长度。最后，它返回这个最大长度。在 main 函数中，它定义了一个示例数组 nums 并调用 lengthOfLIS 函数来计算并打印最长递增子序列的长度。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

int lengthOfLIS(const std::vector<int>& nums) {
    if (nums.empty()) return 0;

    std::vector<int> dp(nums.size(), 1);
    int maxLen = 1;

    for (size_t i = 1; i < nums.size(); ++i) {
        for (size_t j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
        maxLen = std::max(maxLen, dp[i]);
    }

    return maxLen;
}

int main() {
    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    std::cout << "Length of LIS is: " << lengthOfLIS(nums) << std::endl;
    return 0;
}

这段 C++代码实现了动态规划算法来解决最长递增子序列问题。它首先检查输入的数组是否为空，然后创建一个动态规划数组 dp 来存储到当前元素为止的最长递增子序列的长度，并将其初始化为 1。接着，它使用两层循环来更新 dp 数组的值，并在过程中记录下最长递增子序列的长度。最后，它返回这个最大长度。在 main 函数中，它定义了一个示例数组 nums 并调用 lengthOfLIS 函数来计算并打印出最长递增子序列的长度。

Python 版本

def length_of_lis(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)
    max_len = 1

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
        max_len = max(max_len, dp[i])

    return max_len

# Example usage:
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print("Length of LIS is:", length_of_lis(nums))

这段 Python 代码使用动态规划解决了最长递增子序列问题。它首先检查输入列表是否为空，然后创建一个列表 dp 来存储到当前元素为止的最长递增子序列的长度，并将其初始化为 1。接着，它使用两层循环来更新 dp 列表的值，并在过程中记录下最长递增子序列的长度。最后，它返回这个最大长度。代码的最后部分展示了如何使用这个函数，并打印出了示例列表的最长递增子序列的长度。

Java 版本

public class LIS {
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length];
        int maxLen = 1;

        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Length of LIS is: " + lengthOfLIS(nums));
    }
}

这段 Java 代码实现了动态规划算法来解决最长递增子序列问题。它首先检查输入的数组是否为空，然后创建一个动态规划数组 dp 来存储到当前元素为止的最长递增子序列的长度，并将其初始化为 1。接着，它使用两层循环来更新 dp 数组的值，并在过程中记录下最长递增子序列的长度。最后，它返回这个最大长度。在 main 方法中，它定义了一个示例数组 nums 并调用 lengthOfLIS 方法来计算并打印出最长递增子序列的长度。

Rust 版本

fn length_of_lis(nums: Vec<i32>) -> i32 {
    let mut dp = vec![1; nums.len()];
    let mut max_len = 1;

    for i in 1..nums.len() {
        for j in 0..i {
            if nums[i] > nums[j] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
        max_len = max_len.max(dp[i]);
    }

    max_len
}

fn main() {
    let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
    println!("Length of LIS is: {}", length_of_lis(nums));
}

这段 Rust 代码实现了动态规划算法来解决最长递增子序列问题。它首先创建一个动态规划向量 dp，用于存储到当前元素为止的最长递增子序列的长度，并将其初始化为 1。接着，它使用两层循环来更新 dp 向量的值，并在过程中记录下最长递增子序列的长度。最后，它返回这个最大长度。在 main 函数中，它定义了一个示例向量 nums 并调用 length_of_lis 函数来计算并打印出最长递增子序列的长度。

总结

上述代码段展示了如何使用动态规划（Dynamic Programming, DP）算法来解决最长递增子序列（Longest Increasing Subsequence, LIS）的问题。无论是在 Go, C++, Python, Java 还是 Rust 语言中，核心算法的逻辑是一致的，主要步骤如下：

初始化一个数组（或向量）dp，其长度与输入数组 nums 相同。dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始时，每个元素至少可以构成长度为 1 的子序列，因此 dp 数组的所有元素初始化为 1。
使用两层循环来填充 dp 数组：
- 外层循环遍历 nums 数组的每个元素。
- 内层循环遍历当前元素之前的所有元素，检查是否可以形成递增序列。如果 nums[i] 大于 nums[j]（其中 j < i），则尝试更新 dp[i] 为 dp[j] + 1 和当前 dp[i] 的较大值。
在内层循环中，每次更新 dp[i] 后，同时更新一个变量 max_len，该变量用于追踪到目前为止发现的最长递增子序列的长度。
最终，max_len 将包含整个数组的最长递增子序列的长度，这个值被返回作为问题的解。

这种解法的时间复杂度为 O(n^2)，其中 n 是输入数组 nums 的长度。这是因为需要双重循环遍历数组来构建 dp 数组。尽管这种方法不是最优的（存在 O(n log n) 的解法），但它相对简单且易于理解，适合作为动态规划入门问题的示例。

hot-100