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