### 完整题目描述 **题目：最长递增子序列（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 示例代码 ```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 示例代码 ```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 示例代码 ```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 ``` **码小课网站中有更多相关内容分享给大家学习**，包括算法原理、优化方法、面试技巧等，帮助大家更好地掌握算法知识。