完整题目描述

题目： 一维动态规划——最长递增子序列（Longest Increasing Subsequence, LIS）

题目描述： 给定一个无序的整数数组，找出其中最长递增子序列的长度。递增子序列是指序列中的每个数字都比它前面的数字大（但可以不连续）。

示例：

• 输入: [10, 9, 2, 5, 3, 7, 101, 18]
• 输出: 4
• 解释: 最长的递增子序列是 [2, 3, 7, 101]，它的长度为 4。

要求：

• 请使用一维动态规划的方法解决此问题。
• 给出 PHP、Python、JavaScript 三种语言的实现代码。

PHP 实现

function lengthOfLIS($nums) {
    $n = count($nums);
    if ($n <= 1) return $n;
    
    $dp = array_fill(0, $n, 1); // 初始化dp数组，每个元素至少为1
    $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):
    n = len(nums)
    if n <= 1:
        return n
    
    dp = [1] * n  # 初始化dp数组，每个元素至少为1
    maxLength = 1  # 最长递增子序列的初始长度
    
    for i in range(1, n):
        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); // 初始化dp数组，每个元素至少为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

在解决这个算法问题时，我们使用了动态规划的思想，通过构建一个一维数组 dp 来记录以每个位置结尾的最长递增子序列的长度，最终遍历 dp 数组找到其中的最大值即为所求。此解法的时间复杂度为 O(n^2)，空间复杂度为 O(n)。在面试中，这种思路清晰、实现简单的解法往往能受到面试官的青睐。