当前位置： 面试刷题>> 最长递增子序列(经典算法150题)
### 题目描述
**最长递增子序列（Longest Increasing Subsequence, LIS）** 是一个经典的算法问题。给定一个未排序的整数数组，找到该数组的一个子序列，使得这个子序列的元素是严格递增的，并且这个子序列的长度尽可能长。请编写一个函数来找到这个最长递增子序列的长度。
### 示例
**输入**: `[10, 9, 2, 5, 3, 7, 101, 18]`
**输出**: `4`
**解释**: 最长的递增子序列是 `[2, 3, 7, 101]`，它的长度为 4。
### PHP 示例代码
```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 示例代码
```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
```
以上代码示例均实现了最长递增子序列长度的计算，通过动态规划的方法，以空间换时间，提高了算法的效率。在面试中，除了正确实现算法外，还需要能够清晰地解释算法的思路和复杂度分析。