完整题目描述

题目：最长递增子序列（Longest Increasing Subsequence, LIS）

给定一个未排序的整数数组，找出该数组中的最长递增子序列的长度。递增子序列指的是序列中元素的顺序满足严格递增的序列（即 nums[i] < nums[j]，其中 i < j）。

示例 1:

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

示例 2:

输入: [0,1,0,3,2,3]
输出: 4 
解释: 最长的递增子序列是 [0,1,2,3]，它的长度是 4。

注意:

• 你可能需要用到动态规划（Dynamic Programming, DP）的思想来解决这个问题。
• 给定的数组长度不会超过 1000。

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):
    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

码小课网站中有更多相关内容分享给大家学习，包括算法原理、优化方法、面试技巧等，帮助大家更好地掌握算法知识。