当前位置： 面试刷题>> 一维动态规划(经典算法150题)
### 完整题目描述
**题目**： 一维动态规划——最长递增子序列（Longest Increasing Subsequence, LIS）
**题目描述**：
给定一个无序的整数数组，找出其中最长递增子序列的长度。递增子序列是指序列中的每个数字都比它前面的数字大（但可以不连续）。
**示例**：
- 输入: `[10, 9, 2, 5, 3, 7, 101, 18]`
- 输出: 4
- 解释: 最长的递增子序列是 `[2, 3, 7, 101]`，它的长度为 4。
**要求**：
- 请使用一维动态规划的方法解决此问题。
- 给出 PHP、Python、JavaScript 三种语言的实现代码。
### 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):
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 实现
```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)。在面试中，这种思路清晰、实现简单的解法往往能受到面试官的青睐。