题目描述

最长递增子序列（Longest Increasing Subsequence, LIS） 是一个经典的算法问题。给定一个未排序的整数数组，找到该数组的一个子序列，使得这个子序列的元素是严格递增的，并且这个子序列的长度尽可能长。请编写一个函数来找到这个最长递增子序列的长度。

示例

输入: [10, 9, 2, 5, 3, 7, 101, 18]

输出: 4

解释: 最长的递增子序列是 [2, 3, 7, 101]，它的长度为 4。

PHP 示例代码

function lengthOfLIS($nums) {
    $n = count($nums);
    if ($n <= 1) {
        return $n;
    }
    
    $dp = array_fill(0, $n, 1); // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
    $maxLength = 1;
    
    for ($i = 1; $i < $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($nums[$i] > $nums[$j]) {
                $dp[$i] = max($dp[$i], $dp[$j] + 1);
            }
        }
        $maxLength = max($maxLength, $dp[$i]);
    }
    
    return $maxLength;
}

// 示例用法
$nums = [10, 9, 2, 5, 3, 7, 101, 18];
echo lengthOfLIS($nums); // 输出 4

Python 示例代码

def lengthOfLIS(nums):
    if not nums:
        return 0
    
    dp = [1] * len(nums)
    maxLength = 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)
        maxLength = max(maxLength, dp[i])
    
    return maxLength

# 示例用法
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lengthOfLIS(nums))  # 输出 4

JavaScript 示例代码

function lengthOfLIS(nums) {
    const n = nums.length;
    if (n <= 1) return n;
    
    const dp = new Array(n).fill(1);
    let maxLength = 1;
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLength = Math.max(maxLength, dp[i]);
    }
    
    return maxLength;
}

// 示例用法
const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLIS(nums)); // 输出 4

以上代码示例均实现了最长递增子序列长度的计算，通过动态规划的方法，以空间换时间，提高了算法的效率。在面试中，除了正确实现算法外，还需要能够清晰地解释算法的思路和复杂度分析。